# Minimum Spanning Tree Question

Every minimum spanning tree of a graph has the property that the weight of every non-tree edge (u,v) is at least as large as the weight of all the edges on the u-v path of the tree T. Use Kruskals algorithm to show the converse: if a spanning tree T has the above property then it is a minimum spanning tree.

Suppose that T is a spanning tree that has this property and suppose that the edges of the graph are sorted in nondecreasing order of weight with ties broken in favor of the edges of T. Prove that Kruskals algorithm
outputs the tree T.
###### Who is Participating?

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Is this homework?
For the last claim, it should suffice to observe that Kruskal's algorithm will not add any edge that violates the property.
and if you believe that Kruskal's algorithm produces a Minimum Spanning Tree, then the first claim follows from the second.
0

Experts Exchange Solution brought to you by