Let G be a connected weighted graph whose edges have distinc

Let G be a connected weighted graph whose edges have distinct weights. Prove that G has unique minium spanning tree

Solution

Proof by contradiction :
Lets assume that the graph has 2 MST - MST1 and MST2. Let E be the set of edges present in MST2 but not in MST1.

Consider MST1. If this is a minimum spanning tree, adding an edge to it should create a cycle. Consider adding an edge \'e\' from E. Add \'e\' to MST1. This would create a cycle. Hence, this new tree ( say T ) is just 1 edge away from being a MST. To make a MINIMUM spanning tree out of it, you have to remove the most expensive edge in the cycle. Because all the edges have different weights, the most expensive edge will be only one of its kind. If \'e\' is the most expensive edge, then, you don\'t get multiple MSTs. If \'e\' is not the most expensive edge, then MST1 was not a MINIMUM spanning tree.