证明存在一个顶点的最小生成树，该顶点总是包含该顶点的最短边

Question

假设e是赋权图中与顶点v关联的边，使得e的权重不超过与v关联的任何其他边的权重。证明存在包含此边的最小生成树。

Answer 1

矛盾的证明

假设存在一个顶点v，使得MST不使用其最小权重边e，而是使用另一个入射边，我们称之为x。现在，假设我们将边e添加回MST，从而形成一个循环。现在，我们可以删除该周期中使用的前一条边x。在这一点上，我们有了另一个MST，其总体成本低于之前找到的生成树。这是矛盾的，因为如果具有边x的生成树比具有边e的生成树具有更高的成本，则它实际上不是MST。