Here's a question from CLRS ch23, MSTs:

Let T be a minimum spanning tree of a graph G, and let L be the sorted list of the edge weights of T. Show that for any other minimum spanning tree T' of G, the list L is also the sorted list of edge weights of T'.

My argument is, every MST must have exactly |V| - 1 edges, and for a cut, if the two MSTs choose different edges, then these edges must have exactly the same weight, because if T' takes a crossing edge of weight more than some corresponding edge in T for that cut, T' is no longer an MST, and if T' takes an edge of weight less, the original spanning tree (T) is no longer an MST. Both lead to a contradiction.

Is this argument correct/enough for this question? Is there a stronger/better argument?

  • There are a couple of proofs to that statement in that question. Your approach is nice although the very last part of your argument is probably flawed. It turns out there seems still a long way to go even though you have made quite some progress. – Apass.Jack Oct 27 at 13:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.