证明没有最小生成树包含最大加权边

Question

假设有一个图G，它的所有边都有对应于不同整数的权重。因此，没有两个边缘具有相同的权重。令E为G的所有边。令emax为E中具有最大权重的边。图G的另一个特性是每个边e都属于G中的某个循环。

我必须证明G的最小生成树不包含边缘emax。

我可以理解为什么如此，因为所有边缘都是不同的，并且每个边缘都属于一个循环，所以最小生成树算法可以简单地在包含emax的循环中选择权重较低的边缘。但是我不确定如何具体证明这一点。

Answer 1

这与最小生成树的循环属性有关，该循环属性基本上是说，给定图中的一个循环，权重最大的边不属于MST（通过上面链接中的矛盾很容易证明）。因此，由于边沿emax属于一个循环，因此它一定不能在MST中。