Welcome to our community

Be a part of something great, join today!

need hint on weighted graphs

find_the_fun

Active member
Feb 1, 2012
166
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

Indicium Physicus
Staff member
Jan 26, 2012
4,191
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

New member
Jan 29, 2012
8
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.