Introduction to graph theory/Proof of Theorem 2

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.