# Sorted list of edges for two different MSTs in a graph

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