[Math] the proof that adding an edge to a spanning tree creates a cycle

graph theoryproof-verification

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?

Best Answer

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.