0
$\begingroup$

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.

Not sure if I'm going about this proof correctly.

$\endgroup$
  • $\begingroup$ Why must $G'$ be connected? $\endgroup$ – Santana Afton Feb 25 '17 at 14:26
  • $\begingroup$ @JazzyMatrix Not sure anymore. My proof is wrong but I had to turn it in. $\endgroup$ – HiPolyEraser Feb 25 '17 at 23:09
  • $\begingroup$ 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. $\endgroup$ – Santana Afton Feb 25 '17 at 23:44
  • $\begingroup$ @JazzyMatrix Alright I try thanks $\endgroup$ – HiPolyEraser Feb 26 '17 at 0:25

Your Answer

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

Browse other questions tagged or ask your own question.