$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle
Could anyone please be so kind to check my proof? That would be very much appreciated. Thank you in advance.
My proof:
'$\rightarrow$' Assume $G$ is a tree. Then by definition it is connected. Furthermore, there is a unique $u, v$-path for every $u,v \text{ in } G$. For arbitrary $u$ and $v$, let this path be $u=u_1\rightarrow u_2\rightarrow \dots \rightarrow u_k=v$. Assume $\nexists$ an edge $e=\{u_i,u_j\}$ for some vertices $u_i, u_j \text{ } (j>i)$ in this path. Now add this edge $e=\{u_i,u_j\}$. Then we can follow the original $u,v$-path until we arrive at $u_j$ and then return to $u_i$ via $e$. Hence this is a cycle.
'$\leftarrow$' Assume $G$ contains no cycles but if you add one edge you create exactly one cycle. To prove that $G$ is a tree we only need to prove connectedness, since it is already given that $G$ contains no cycles. Reason by contradiction. Assume that $G$ is not connected. Then $\exists u \exists v \text{ }(u\neq v)$ in $G$ s.t. $\nexists$ an edge $\{u,v\}$. Add this edge. This will not create a cycle. But this contradicts our original assumption. Hence $G$ must be connected, and thus $G$ is a tree.
Best Answer
To prove "exactly one" in the $\rightarrow$ direction, suppose the addition of $(u,v)$ created (at least) two cycles. Both must include $(u,v)$ else they were cycles before. However, we now can go from $u$ to $v$ along two different paths in the tree, a contradiction.
In the $\leftarrow$ direction, if $G$ is not connected, choose $u,v$ from different components. Then adding $(u,v)$ cannot create a cycle.