Adding Edge to Tree Creates One Cycle

Theorem

Adding a new edge to a tree can create no more than one cycle.

Proof

From Equivalent Definitions for Tree, adding an edge creates at least one cycle.

Suppose that adding an edge $\left({u, v}\right)$ to a tree $T$ creates two or more cycles.

Let these two cycles be $\left({u, v, \ldots, u_1, u_2, \ldots, u}\right)$ and $\left({u, v, \ldots, v_1, v_2, \ldots, u}\right)$.

By removing the edge $\left({u, v}\right)$ from this cycle, we have two paths from $v$ to $u$:

• $\left({v, \ldots, u_1, u_2, \ldots, u}\right)$;
• $\left({v, \ldots, v_1, v_2, \ldots, u}\right)$.

But that means $T$ has more than one path between two nodes.

From Paths in Trees are Unique, that means $T$ can not be a tree.

Hence the result.

$\blacksquare$