Kruskal算法的正确性 显然T是生成树。 。按在算法中加边顺序，T中边是e1,e2,ek-,cken-1 ·假设T不是最小生成树。对于任意给定的一棵最小生成树 T’,存在唯一的k,使得eET,,，且e,∈ET,使得I≤i<k).设T? 是这样的一棵最小生成树，使得上述的k达到最大。 ·根据前述引理，T中存在边e',e'不属于T,使得T*=T’- {e'U{e}也是生成树。e'eT与e1,e2.ek1不会构成回路， 因此w(e)2w(e).所以w(T*)sw(T),即T*也是最小生成树。 但T*包含e1,e2ck-1ek,矛盾。Kruskal算法的正确性  显然T是生成树。  按在算法中加边顺序，T中边是e1 ,e2 ,…ek-1 , ek ,…en-1。  假设T不是最小生成树。对于任意给定的一棵最小生成树 T’, 存在唯一的k, 使得ekET’ ，且eiET’使得(1ik). 设T’ 是这样的一棵最小生成树，使得上述的k达到最大。  根据前述引理，T’中存在边e’ ，e’不属于T, 使得T*=T’- {e’}⋃{ek }也是生成树。 e’T’与e1 ,e2 ,…ek-1不会构成回路， 因此w(e’)w(ek ). 所以w(T*)w(T’), 即T*也是最小生成树。 但T*包含e1 ,e2 ,…ek-1 ,ek，矛盾