Introduction to graph theory/Proof of Corollary 3

From Wikiversity
Jump to navigation Jump to search

Statement[edit | edit source]

A graph is a tree if and only if for every pair of distinct vertices , there is exactly one -path.

Corollary of[edit | edit source]

Theorem 2: A graph is a forest if and only if for every pair of distinct vertices , there is at most one -path.

Proof[edit | edit source]

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 , there is at least one -path. The proof should now be evident, but for completeness:

If graph is not a tree, it is either not a forest, or not connected. If is not a forest, by Theorem 2, there exists a pair of vertices with more than one -path. If is not connected, there exists a pair of vertices with no -path. Thus if is not a tree, it is not the case that each pair of vertices has precisely one -path.

If graph is a tree, fix a pair of vertices . As G is a forest, by Theorem 2, there exists at most one -path. Since is connected, there is at least one -path. Thus there is exactly one -path. Since we have proved this for any fixed pair of vertices , it follows that if G is a tree, each pair of vertices has precisely one path.

Comments[edit | edit source]