Can two Minimum Spanning Trees for the same graph have different edge weights?

Question

A graph can have many different Minimum Spanning Trees (MSTs), but can different MSTs have different sets of edge weights? For example, if an MST uses edge weights {2,3,4,5}, must every other MST have edge weights {2,3,4,5}, or can some other MST use a different collection of weights?

What gave me the idea is property that a graph has no unique MST only if its edge weights are different.

Epigrammatist

Have you tried to construct a weighted graph with two lightest spanning trees having different multisets of weights? – Elyot

Answer 1

The sets must have the same weight. Here's a simple proof: suppose they don't. Let's let T1 and T2 be MSTs for some graph G with different multisets of edge weights.

Sort those edges into ascending order of weight. Since the two multisets of weights aren't the same, look at where the weights first diverge. There will end up being some smallest weight w* in either T1 or T2 (assume WLOG, that it's in T1) where T1 and T2 have the same number of edges of all weights less than w*, but T1 has more edges of weight w* than T2. Intuitively, edges of weight w* is where T1 "gets ahead" of T2.

Now, consider the set of edges of weight w* in T1; let's call them W*. Consider what happens when you add any of those edges into T2. Every time we do this, it will close a cycle in T2. Note that the newly-added edge e can't be the maximum-weight edge on that cycle; if it were, then by the cycle property we'd be guaranteed that e can't appear in any MST, but we know for a fact that it is in one (namely, T1). Therefore, there must be some edge on the cycle whose weight is greater than or equal to w*.

If one of those edges has weight strictly greater than w*, then we can decrease the cost of T2 by deleting that edge. That would be impossible, though, because we know that T2 is an MST.

Therefore, we know that there is some other edge in the cycle whose weight is equal to w*. If any of those edges are not in T1, then choose any one and remove it. Notice that we've just swapped an edge in T2 for an equal-weight edge in T1. Because there are more edges of weight w* in T1 than in T2, we can't do this forever and eventually we'll run into the case where the cycle was closed and all the max-weight edges are of weight w* and come from T1.

So what happens in this case? Well, think about the cycle C that was closed when we added the edge that triggered this. We're going to show that in this case, T1 can't be an MST, contradicting our initial assumption and giving us the result we want.

Let C* be the set of edges in C that have cost less than w*. Process those edges in order of weight, adding them to T1 one at a time. Each time we do so, we close a cycle. The max-weight edge in that cycle can't be the edge we added from T2 (because otherwise by the cycle property that edge shouldn't have been in T2 in the first place). Therefore, either the max-weight edge either has weight greater than the edge from T2 (in which case we delete it, contradicting that T1 was an MST) or it has the same weight. Eventually, we end up transforming T1 so that it has the same set of edges of cost less than w* that T2 does. But that's a problem, because at that point we know that we would have the cycle C arising in T1, meaning that T1 isn't an MST. This gives us the contradiction we need.

Hope this helps!

Seleucid

I don't follow your last paragraph. When you take an edge from C* and move to T1, at the same time you remove an edge of the same weight from T1. But since T1 and T2 has equal number of edges of weight less than w*, this does not mean C will end up all being in T1. You could have a cycle A-B-C-D with weight AB:w, BC:w, CD:w', DA:w' where w'<w. AD, CD, and AB are in T1 but AB and BC are in T2. When you add BC over to T1, you remove AB from T1. But AB is also in T2 so you are not getting the contradiction cycle in T1. T1 and T2 have same number of edges of weight less than w*. Am i wrong? – Jansenism