Proving that no minimum spanning tree contains the maximum weighted edge

algorithm graph minimum-spanning-tree
user65663 picture user65663 · Nov 27, 2013 · Viewed 10.5k times · Source

Let's say there's Graph G such that it all its edges have weights that correspond to distinct integers. So no two edge has the same weight. Let E be all the edges of G. Let emax be an edge in E with the maximum weight. Another property of Graph G is that every edge e belongs to some cycle in G.

I have to prove that no minimum spanning tree of G contains the edge emax.

I can see why this is true, since all edges are distinct and every edge belongs to a cycle, the minimum spanning tree algorithm can simply choose the edge with lower weight in the cycle that contains emax. But I'm not sure how to concretely prove it.

Answer

Dimitris picture Dimitris · Nov 27, 2013

This is related to the Cycle Property of the Minimum Spanning Tree, which is basically saying that given a cycle in a graph the edge with the greatest weight does not belong in the MST (easily proven by contradiction in the link above). Thus since the edge emax belongs to a cycle it must not be in the MST.

Related questions

Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Is Minimum Spanning Tree afraid of negative weights?

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?. I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to …

Read More
How is a minimum bottleneck spanning tree different from a minimum spanning tree?

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum spanning tree). Please …

Read More