假设非严格次小生成树与最小生成树有至少两条边不同,那么按照kruskal算法枚举到第一条不在最小生成树的边但在非严格次小生成树中的边,此时两边的点集通过后续的边联通了,后续的边权值一定大于等于那天最小生成树中的边,将这条边与后续联通的某条边替换,此时不同边少了一条且非严格次小生成树权值没有变大。只要有大于1条的不同边,就可以一直进行这个操作。直到只有一条边不同,这就与条件矛盾。
假设严格次小生成树与最小生成树有至少两条边不同,那么按照kruskal算法枚举到第一条不在最小生成树的边但在严格次小生成树中的边,此时两边的点集通过后续的边联通了,后续的边权值一定大于等于最小生成树中的边,如果这条边与后加的边权重相同,那么可以用树边替换掉这个后续边,总权值大小不边,不同边数量减1,然后继续看后面的边;如果后续边权值大于树边,那么将树边替换掉后续边,总权值下降,与这棵树是严格次小生成树矛盾,因为找到了一个边不同且权值更小的树。