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
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.