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.
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.