# Introduction to graph theory/Proof of Corollary 3

Jump to navigation Jump to search

## 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.