As per Wikipeida, adding one more edge anywhere to any spanning tree would create a cycle. What's the proof?

I saw this property used in a proof about a unique spanning tree for graphs with edges with unique weights. In a class a teacher once said you can use properties/theorems given earlier on in the textbook to where the question is being asked. When you're trying to prove something when can you use a property or theorem like this one?


Proof by contradiction:

Assume that adding an edge to a spanning tree does not create a cycle. Suppose we add edge $(u,v)$ between two vertices $u$ and $v$ to $T$, a spanning tree of a graph $G$. Since we assumed adding an edge to $T$ does not create a cycle, this implies that prior to the insertion of $(u,v)$, there was no path from $u$ to $v$ in $T$. But $T$ is a spanning tree, so such a path must have existed and we have arrived at a contradiction.

Therefore, adding an edge to a spanning tree creates a cycle.

  • 10
    $\begingroup$ There's really no need to phrase this as a proof by contradiction: you can just say "since $T$ is connected, there's a $u,v$-path in $T$; adding the new edge $uv$ to this path yields the desired cycle". $\endgroup$ Feb 27 '16 at 4:17
  • 1
    $\begingroup$ @GregoryJ.Puleo How would you prove it introduces exactly one cycle $\endgroup$
    – Anush
    Nov 5 '18 at 11:44
  • 1
    $\begingroup$ @Anush consider it creates two distinct cycles $u,v, x_1, ..., u$ and $u, v, y_1, ..., u$. Then remove edge $u,v$ and we have two paths from $v$ to $u$ in original tree- a contradiction. $\endgroup$ Dec 28 '19 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.