# Introduction to graph theory/Proof 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.
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\ge 3$) be the vertices on $C$ in order. Then there are two distinct $v_1,v_2$-paths, namely $v_1v_2$ and $v_1v_nv_{n-1}\ldots v_3v_2$.
Now suppose that $G$ is not a forest, but has two distinct $u,v$-paths, namely $ua_1a_2\ldots a_nv$ and $ub_1b_2\ldots b_mv$. We would like to say that these create a cycle $ua_1\ldots a_nvb_mb_{m-1}\ldots b_1u$. 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_ia_{i+1}\ldots a_nvb_mb_{m-1}\ldots b_j$. By our choice of $i$, clearly no vertex appears more than once.