引理（更换生成树的边) 。T与T均是图G的生成树，若eeET且eET,则必有e'∈ET, e'ET,且T-{eU{e'}和T'-{e'U{e}均是G的生成树。 ●设e=uv,T-{e}必含两个连通分支，设为T1,T2。因T'是连 通图，T'中有v-通路，其中必有一边满足其两个端点x,y 分别在T,T,中，设其为e',显然T-{eU{e'}是生成树。 而T’-{e'}中x,y分属两个不同的连通分支，但在T*=T' {e'U{e}中，xu-通路+e+vy通路是一条xy-通路，因此T' {e}U{e}连通，从而T'-{e'}U{e}是生成树。 引理（更换生成树的边）  T与T‘均是图G的生成树，若eET且eET’，则必有e'ET’, e'ET , 且T-{e}⋃{e'}和T'-{e'}⋃{e}均是G的生成树。  设e=uv, T-{e}必含两个连通分支，设为T1 , T2。因T'是连 通图，T'中有uv-通路，其中必有一边满足其两个端点x,y 分别在T1 , T2中，设其为e'，显然T-{e}⋃{e'}是生成树。 而T’-{e’}中x,y分属两个不同的连通分支，但在T*=T’- {e’}⋃{e}中，xu-通路+e+vy通路是一条xy-通路，因此T’- {e’}⋃{e}连通，从而 T'-{e'}⋃{e}是生成树。 T1 T2 u x v y e e