MHB How Does Unique Edge Weighting Guarantee a Singular Minimum Spanning Tree?

[find_the_fun]

Prove that if a weighted graph has unique weights on each edge that there is only 1 minimum spanning tree. Do I need to use an algorithm such as Prim's to show this or do I use properties of weighted graphs?

 

[Ackbach]

Try contradiction. Assume you have two MST's of equal weight. Consider what happens with an edge that's in one MST but not the other (there must be at least one such edge if the MST's are not the same).

 

[Chinta]

Kruskal's Algorithm can be used here as follows:

If edge costs are all distinct then running Kruskal's Algorithm on this graph G(say) creates only a unique sequence of (n-1) edges with edge costs in increasing order. Hence G has a unique minimum spanning tree.