# Introduction to graph theory/Proof of Theorem 2

Jump to navigation Jump to search

## Statement

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

Suppose you have a graph $G$ which is not a forest. Since a forest is defined to be a graph containing no cycles, it is clear that $G$ must have a cycle $C$ . All cycles have at least three vertices. Let $v_{1},v_{2},\ldots ,v_{n}$ (with $n\geq 3$ ) be the vertices on $C$ in order. Then there are two distinct $v_{1},v_{2}$ -paths, namely $v_{1}v_{2}$ and $v_{1}v_{n}v_{n-1}\ldots v_{3}v_{2}$ .

Now suppose that $G$ is a forest, but has two distinct $u,v$ -paths, namely $ua_{1}a_{2}\ldots a_{n}v$ and $ub_{1}b_{2}\ldots b_{m}v$ . We would like to say that these create a cycle $ua_{1}\ldots a_{n}vb_{m}b_{m-1}\ldots b_{1}u$ . However, a cycle can only include each vertex once, and it is possible that one of the $b_{i}$ is equal to one of the $a_{j}$ . To that end, write $a_{0}=b_{0}=u$ and $a_{n+1}=b_{m+1}=v$ . Let $i$ be the largest value of $i<=n$ such that $a_{i}=b_{j}$ for some $j$ . Then we find a cycle, namely $a_{i}a_{i+1}\ldots a_{n}vb_{m}b_{m-1}\ldots b_{j}$ . By our choice of $i$ , clearly no vertex appears more than once.