Introduction to graph theory/Proof of Corollary 3
From Wikiversity
Contents |
[edit] Statement
A graph is a tree if and only if for every pair of distinct vertices u,v, there is exactly one u,v-path.
[edit] Corollary of
Theorem 2: A graph is a forest if and only if for every pair of distinct vertices u,v, there is at most one u,v-path.
[edit] Proof
A tree is defined to be a connected forest. Furthermore, a graph is defined to be connected if and only if for every pair of distinct vertices u,v, there is at least one u,v-path. The proof should now be evident, but for completeness:
If graph G is not a tree, it is either not a forest, or not connected. If G is not a forest, by Theorem 2, there exists a pair of vertices u,v with more than one u,v-path. If G is not connected, there exists a pair of vertices u,v with no u,v-path. Thus if G is not a tree, it is not the case that each pair of vertices has precisely one u,v-path.
If graph G is a tree, fix a pair of vertices u,v. As G is a forest, by Theorem 2, there exists at most one u,v-path. Since G is connected, there is at least one u,v-path. Thus there is exactly one u,v-path. Since we have proved this for any fixed pair of vertices u,v, it follows that if G is a tree, each pair of vertices has precisely one path.
