其实这个证明与前面那个证明很像
假设最终生成的生成树不包含这\(m-k\)条边中连接生成森林的两个不连通节点的最小的边，那么我们从这些最小的边中任选一条边加入到树中会形成一个环，而且这个环（除了加入的这条最小边）一定存在一条边不是最开始的\(k\)条边中的某一条（因为如果这个环除了加入的最小边，剩余的边都是\(k\)条边中的某一条的话，那么这条加入的最小的边就是连接生成森林的两个连通节点的边了，根本不在我们的考虑范围之内），把这条边删掉换成这个最小的边，根据“向树加入一条边形成一个环，删除环上任意一条边后的图仍然是树”可得结论
然后用数学归纳法可以证明Kruscal的正确性
从以上证明过程也可看出，我们生成MST时（比如做Kruscal时），任选这\(m-k\)条边中连接生成森林的两个不连通节点的最小的边，最终一定都能生成一个MST
标签：推论,一条,加入,P364,生成,蓝书,最小,条边,证明 From： https://www.cnblogs.com/dingxingdi/p/18010749