Question

Problem 4 

Let G = (V. E) be an undirected, connected graph with weight function w : E → R. Furthermore, suppose that E 2 |V and that all edge weights are distinct. Prove that the MST of G is unique (that is, that there is only one minimum spanning tree of G).

Answer 1

To prove that A graph having all edges weight distinct has unique MST.

proof using cycle property:

Let Graph G=(V,E) be the original graph.

Assume there are two distinct MSTs T1=(V,E1) and T2=(V,E2).
Since T1 and T2 are distinct, the sets E1 and E2 is not empty, let edge e belong to (E1−E2).

Since e not belong to set E2, adding it to T2 creates a cycle.
By cycle property the most expensive edge of this cycle (call it e′) does not belong to any MST.
But
If e′=e then e′ belong to E1 (because e belong to (E1−E2))
If e′≠e then e′ belong to E2
both cases are contradicting with the fact that e′ is not in any MST.
Hence our Assumption that T1 and T2 are two distinct MSTs is wrong.
Therefore ,it is true that A graph having all edges weight distinct has unique MST.