1
$\begingroup$

this is not a homework but I need to understand it before my exam tomorrow.

How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are distinct?

you can assume that the graph has two distinct MST.

Any help is appreciated. Thank you

$\endgroup$
3
$\begingroup$

Hint: Consider the most expensive edge that is in one of the two spanning trees but not in the other. Removing it will make its tree fall apart in two pieces. But you can connect it back together again by adding a cheaper edge from the other spanning tree. This shows that the tree was not minimal to begin with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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