0
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.