Adding Edge to Tree Creates One Cycle

From ProofWiki
Jump to navigation Jump to search

Theorem

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


Proof

From Equivalent Definitions for Finite 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 Path in Tree is Unique, that means $T$ can not be a tree.

Hence the result.

$\blacksquare$