设T1和T2是连通图G的两棵生成树,a是在T1中但不在T2中的一条边。证明存在边b它在T2中但不在T1中,使得(T1-{a})U

设T₁和T₂是连通图G的两棵生成树,a是在T₁中但不在T₂中的一条边。证明存在边b它在T₂中但不在T₁中,使得(T₁-{a})U{b}和(T₂-{b})U{a}都是G的生成树。
【正确答案】：证明:设G的两棵生成树T₁和T₂,边a=(u,v),a∈T₁且a∉T₂生成树中所含的边数=n-1。
 则G1=(T₁-{a})中所含边数=n-2。显然G₁是不连通的,且W(G₁)=2。
 两个连通分量分别是T₁₁和T₁₂。
 树中任意两个顶点之间只有一条路相连,故在G₁中,u与v之间不存在路。不妨设 U∈T₁₁,v∈T₁₂。T₁₁中任意点与u之间均有路,T₁₂中任意点与v之间均有路。
因T₂是不含边a的生成树,故在T₂中,u与v之间存在路p,p中必定包含一条边b∉T₁(否则在T₁中u与v之间存在路),b=(x,y),x∈T₁₁,y∈T₁₂。
在(T₁-{a}) U {b}中,对于T₁₁中的任意顶点q,有路连通到顶点x,通过边b,可以与顶点y相连,进而与T₁₂中的任意顶点t之间有路存在.故T₁中任意点与T₁₂中任意点之间存在路,即(T₁-{a})U{b}是连通的,且所含边数为n-1,由定义可知,这是G的一棵生成树。
类似的可证明(T₂-{b})U{a}也是G的生成树。