Introduction to graph theory/Proof of Corollary 3

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.

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.

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.