Kruskal生成的树是T2，这样，因为T2！=T1（如果相等我们的Kruskal就最优了，就不用证了），所以至少有一条边e，e在T1中，同时e不在T2中。这个与众不同的e就是我们的切入点。可以想象，如果我们把e在T1中去掉，T1就变成了两部分，即Ta和Tb，我们知道 {Ta中的点}V{Tb中的点} = V（就是Ta中的点并上Tb中的点就是我们G中的点集V），所以在T2中，一定有一条边f（f！=e），f的一个点在{Ta中的点}，f的另一个点在{Tb中的点}。根据我们的Greedy算法Kruskal，我们没有选e，是因为e在我们的图中造成了回路。在进一步想，有回路是因为我们先选了f，这就说明cost(f) <= cost(e)。 （恩，这就是我们的重点啊，笑一个O(∩_∩)O~）
下面的也就很显然了，我们考虑构造一棵新的树，T3，对于T3 = E(T1) - e + f，也就是T3中的边是T1中的所有边除了e，同时加上边f。
1）很显然，我们知道T3是一棵spanning tree，f连通了由去掉e而分隔的两部分。
2）很显然，T3的cost是<= T1的cost的。 因为cost(f) <= cost(e)，且其他不变。即T3是MST。
所以同个上面的构造，我们就构造出了一棵树，这个树是MST，同时它比T1更接近于T2。（多了一条common的边）
我们知道T1和T2对多有n条边是不同的，通过上面的步骤，我们可以经过n次变换，得到T2，同时cost <=T1，所以，T2是MST。证毕。