Welcome to our community

Be a part of something great, join today!

need hint on weighted graphs


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


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


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