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,\dots ,v_n$ (with $n\ge 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}\dots v_3{v}_2$.

Now suppose that $G$ is a forest, but has two distinct $u,v$-paths, namely $u{a}_1{a}_2\dots a_{n}v$ and $u{b}_1{b}_2\dots b_{m}v$. We would like to say that these create a cycle $u{a}_1\dots a_{n}v{b}_m{b}_{m-1}\dots 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}\dots a_{n}v{b}_m{b}_{m-1}\dots b_j$. By our choice of $i$, clearly no vertex appears more than once.