# Find a diffrent minimal spanning tree for a graph

For my homework I have a problem that I can't solve and it makes me wonder about 2 different MST:

Let $$G=(V,E)$$ be a graph that has a minimum spanning tree $$T$$.

I want to find another minimum spanning tree $$T'$$ that has at least 1 different edge $$e'$$ such that the weight of $$e'$$ is differ from any weight of edges in $$T$$.

If $$T'$$ doesn't exist I can claim that every 2 different MST must have the same weight for each edge.

My intuition says that this claim is wrong but on the other hand I can't find example of $$T'$$ to contradict this claim.

## 1 Answer

You cannot find such a MST. Every two minimal spanning trees must have the same multiset of edge-weights. Actually you can find the proof in the link that Raphael added:

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?