[Solved]: Find a diffrent minimal spanning tree for a graph

Problem Detail: 

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.

Asked By : Aviad Chmelnik

Answered By : Gari BN

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?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19049

3.2K people like this

 Download Related Notes/Documents