# Introduction to graph theory/Proof 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.
Suppose you have a graph ${\displaystyle G}$ which is not a forest. Since a forest is defined to be a graph containing no cycles, it is clear that ${\displaystyle G}$ must have a cycle ${\displaystyle C}$. All cycles have at least three vertices. Let ${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$ (with ${\displaystyle n\geq 3}$) be the vertices on ${\displaystyle C}$ in order. Then there are two distinct ${\displaystyle v_{1},v_{2}}$-paths, namely ${\displaystyle v_{1}v_{2}}$ and ${\displaystyle v_{1}v_{n}v_{n-1}\ldots v_{3}v_{2}}$.
Now suppose that ${\displaystyle G}$ is a forest, but has two distinct ${\displaystyle u,v}$-paths, namely ${\displaystyle ua_{1}a_{2}\ldots a_{n}v}$ and ${\displaystyle ub_{1}b_{2}\ldots b_{m}v}$. We would like to say that these create a cycle ${\displaystyle 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 ${\displaystyle b_{i}}$ is equal to one of the ${\displaystyle a_{j}}$. To that end, write ${\displaystyle a_{0}=b_{0}=u}$ and ${\displaystyle a_{n+1}=b_{m+1}=v}$. Let ${\displaystyle i}$ be the largest value of ${\displaystyle i<=n}$ such that ${\displaystyle a_{i}=b_{j}}$ for some ${\displaystyle j}$. Then we find a cycle, namely ${\displaystyle a_{i}a_{i+1}\ldots a_{n}vb_{m}b_{m-1}\ldots b_{j}}$. By our choice of ${\displaystyle i}$, clearly no vertex appears more than once.