When you look at the definition of a tree on Wikipedia, you'll see something like:
In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
The first bit of that definition may seem weird at first. An acyclic undirected graph might make more sense. But it's the first bit of the definition that explicitly highlights an essential property of a tree.
A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique path.
Let's prove it!
Assume graph T is a tree. Let u and v be distinct vertices in that assumed tree. If T has one vertex, then the conclusion is satisfied automatically as there is only one path to get to one vertex.
Now, we must show two parts:
- There is a path.
- There is not more than one path.
The first part is satisfied by our assumption that T is a tree. Recall that trees are acyclic connected graphs. Check ✔️.
Next, to show that the path is unique, suppose that our tree actually has two paths between u and v.
If there are two paths from u to v, we know that these paths start the same way and differ somewhere along the way. Because these paths go to the same end, the paths must converge at the same vertex.
In fact, they must diverge at a common vertex u' and converge at a common vertex v'. Look what that gives us:
u
u'
/ \
x y
\ /
v'
v
We arrived at a contradiction regarding the "acyclic" property of trees. Trees are "acyclic connected graphs." What we have shown above is a cyclic connected graph, not a tree.
Top comments (0)