Proving that no minimum spanning tree contains the maximum weighted edge
algorithm, graph, minimum-spanning-tree
Solution
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.
Problem
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.