定理7.8：克鲁斯科尔算法所得到的图T是最小生成树。证明：首先由定理7.1等价定义（4)(T是无回路图且在T的任两个不相邻的顶点之间添加边，恰得到条回路）知T是G的一棵子树。并由等价定义(2）可知边数为n-1(T是无回路图，且e-n-1)，所以为G的生成树。下面证明T是最小生成树即可
定理7.8:克鲁斯科尔算法所得到的图T是 最小生成树。 证明:首先由定理7.1等价定义(4)(T是无 回路图,且在T的任两个不相邻的顶点之 间添加一边,恰得到一条回路)知T是G的 一棵子树。 并由等价定义(2)可知边数为n-1(T是无回 路图,且e=n-1)，所以为G的生成树。 下面证明T是最小生成树即可
用反证法证明假设T不是G的最小生成树而S是G的生成树并且W(S)<W(T)。在生成树T中有n-1条边。按权从小到大的顺序排列为ei,2.,ek...,e.若e是不在S中的第一条边，也就是说e,e2..,ek-1是S和T的公共边。现在对S进行变换.在S上加边e得到条回路，记为C在C中必有边eeS,但eT否则T中有回路导致矛盾。但因为ei,e2...,ek-是S和T的公共边，eS,所以ei,e2,...,e和e不构成回路，根据克鲁斯科尔算法知w(e）≤w(e否则T应选e)
用反证法证明, 假设T不是G的最小生成树,而S是 G的生成树, 并且 W(S)<W(T)。 在生成树T中有n-1条边。 按权从小到大的顺序排列为e1 ,e2 ,,ek ,,en-1。 若ek是不在S中的第一条边, 也就是说e1 ,e2 ,,ek-1 是S和T的公共边。 现在对S进行变换,在S上加边ek得到一条回路, 记 为C ,在C中必有一边e‘S, 但e’T,否则T中有回 路,导致矛盾。 但因为e1 ,e2 ,,ek-1是S和T的公共边, e‘S,所以 e1 ,e2 ,,ek-1和e’不构成回路, 根据克鲁斯科尔算法知w(ek )≤w(e')(否则T应选e')