Proving that no minimum spanning tree contains the maximum weighted edge

6
votes

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.

3
algorithmgraphminimum-spanning-tree
en.wikipedia.org/wiki/Minimum_spanning_tree#Cycle_property – Geobits
This type of argument is pretty useful in proving optimality properties of general structures, called the cut and paste argument. You can read more in CLRS about it. – sukunrt
Thanks everyone, it's simple now that i know of this – user65663

3 Answers

7
votes

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.

2
votes

Proof by contradiction works here. Suppose you have a minimum spanning tree including the maximum edge. If you remove that edge you have two components no longer connected from each other. Every vertex is in one component or the other. There is a cycle including the maximum edge. Start on a vertex at one side of the maximum edge and move along the cycle. Because you will eventually cycle round to the other side of the maximum edge in the other component you will find - before then - an edge which has one vertex in one of the disconnected components and one vertex in another of the disconnected components. Since the components are disconnected that edge is not in the minimum spanning tree. By adding it to the tree you reconnect the components and create a minimum spanning tree with smaller weight than you started with - so you original minimum spanning tree was not minimum.

0
votes

Does a MST contain the maximum weight edge?

Sometimes, Yes. It depends on the type of graph. If the edge with maximum weight is the only bridge that connects the components of a graph, then that edge must also be present in the MST.