Introduction to graph theory/Proof of Corollary 3

Statement

edit

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

Corollary of

edit

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

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