&o Now we prove T is a minimum spanning tree Suppose t that is not a minimum spanning tree. Thus there is a spanning tree s of G such that W(S<w(T). w(e1)sw(e2)≤sw(ek)≤…sw(en1) Suppose ek that is the first edges, ie el,e2,.sek-I are common edges of T and s There is a simple circuit C that is in E(sUek Then there is an edge e of c that e'Es and eT. 令e1e2y…,ek-1,e'∈S, thus e1,e2…,ek-1ande'≠any circuit By Kruskal's algorithm, w(eksw(e)❖ Now we prove T is a minimum spanning tree ❖ Suppose T that is not a minimum spanning tree. Thus there is a spanning tree S of G such that w(S)<w(T). ❖ w(e1 ) ≤w(e2 ) ≤≤w(ek ) ≤≤w(en-1 ) ❖ Suppose ek that is the first edgeS, i.e. e1 ,e2 ,,ek-1 are common edges of T and S. ❖ There is a simple circuit C that is in E(S∪{ek }. Then there is an edge e' of C that e'S and e'T. ❖ e1 ,e2 ,,ek-1 , e'S, thus e1 ,e2 ,,ek-1 and e'  any circuit. ❖ By Kruskal’s algorithm, w(ek )≤w(e')