# Introduction to graph theory/Proof of Corollary 3

## Statement

A graph is a tree if and only if for every pair of distinct vertices ${\displaystyle u,v}$, there is exactly one ${\displaystyle u,v}$-path.

## Corollary of

Theorem 2: A graph is a forest if and only if for every pair of distinct vertices ${\displaystyle u,v}$, there is at most one ${\displaystyle 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 ${\displaystyle u,v}$, there is at least one ${\displaystyle u,v}$-path. The proof should now be evident, but for completeness:

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

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