# Proof on minimal spanning tree

Suppose $T$ is a minimal spanning tree in a connected graph G. Show that either $T$ contains the $n-1$ smallest edges, or the $n-1$ smallest edges form a subgraph which contains a cycle.

Suppose $T$ is a minimal spanning tree in a connected graph $G$. Also suppose the $n-1$ smallest edges form a subgraph do not contain a cycle. Therefore since $T$ is a tree it has $n-1$ edges and since it is a minimal spanning tree, each edge in $T$ is of minimum weight. So $T$ contains $n-1$ smallest edges.

• Why must $G'$ be connected? – Santana Afton Feb 25 '17 at 14:26
• @JazzyMatrix Not sure anymore. My proof is wrong but I had to turn it in. – HiPolyEraser Feb 25 '17 at 23:09
• Try to still figure it out! Math is all about practice. If you let $H$ be the subgraph given by the $n-1$ smallest edges, consider the statements contrapositive: if $T\ne H$ and $H$ is a forest, then $T$ is not minimal. All you have to do is show that $H$ must be connected, and you're done. – Santana Afton Feb 25 '17 at 23:44
• @JazzyMatrix Alright I try thanks – HiPolyEraser Feb 26 '17 at 0:25