设nk时,结论成立。下证n=k+1时,结论 也成立。 设e=(u,是G中的一条边,由于G中无回 ’G1e(在G删除边所得的子图有两个连 所以 通分支G和G2,设它们的结点数和边数分别为 m1,n1和m2,n2。于是有n1k和n2k,由归纳 假设知 1和 则 m=m1+m2+1=n1-1+n2-1+1=n-1
设n≤k时，结论成立。下证n=k+1时，结论 也成立。 设e=(u,v)是G中的一条边，由于G中无回 路，所以 G-e(在G删除边e所得的子图)有两个连 通分支G1和G2，设它们的结点数和边数分别为： m1，n1和m2，n2。于是有n1≤k和n2≤k，由归纳 假设知：m1 =n1 –1和m2 =n2 -1，则： m=m1＋m2＋1=n1 -1＋n2 -1＋1=n-1
③→④只须证明G是连通的。若不然,设G 有2)个连通分支G1,G2,…,G,G中均无 回路,都是树。由①→②→③可知,m=n1 i=1,…。于是mm+m2+…+m1=m1-1+m2-1 +…+nr1=n1+n2+…+nr′=nt,由于仑2,这 与m=n-1矛盾。所以G是连通图。 ④→⑤只须证明G的每一条边均为桥。设e是 的任意边,删除e得子图G1,G中的边数m1=m 1,G1中的结点数n1=n,m1=m-1=n-1-1=n-2=n12 <n1-1,所以G不是连通图,所以e是桥
③④只须证明G是连通的。若不然，设G 有t(t≥2)个连通分支G1，G2，…，Gt，Gi中均无 回路，都是树。由①②③可知，mi =ni –1， i=1,…,t。于是m=m1＋m2＋…＋mt =n1 -1＋n2 -1 ＋…＋nt -1=n1＋n2＋…＋nt -t=n–t，由于t≥2，这 与m=n–1矛盾。所以G是连通图。 ④⑤只须证明G的每一条边均为桥。设e是 G的任意边，删除e得子图G1，G1中的边数m1 =m- 1，G1中的结点数n1 =n，m1 =m–1=n-1-1=n-2=n1 -2 ＜n1 -1，所以G1不是连通图，所以e是桥
⑤→⑥由于G中每一条边均为桥,因而G中无 回路。又因为G连通,所以G是树。由①→② 知,Vu∈V,Vv∈V,,u与吵之间存在一条 惟一的路。在u与ν之间增加一条新边,就得到 G的一条回路,显然这条回路是惟一的。 ⑥→①只须证明G是连通的,Vu∈,Vv∈V, l却,在u与ν之间增加一条新边u,)就产生G 的一个惟一的回路,故结点和结点连通。由 于u与哗任意的,所以G是连通图
⑤⑥由于G中每一条边均为桥，因而G中无 回路。又因为G连通，所以G是树。由①② 知，uV，vV，u≠v，u与v之间存在一条 惟一的路。在u与v之间增加一条新边，就得到 G的一条回路，显然这条回路是惟一的。 ⑥①只须证明G是连通的，uV，vV， u≠v，在u与v之间增加一条新边(u,v)就产生G 的一个惟一的回路，故结点u和结点v连通。由 于u与v是任意的，所以G是连通图
定理:设T是m阶非平凡的无向树,则T中 至少有两片树叶。 证:因为T是非平凡树所以T中每个顶点的度 数都大于等于1,设T有k片树叶,则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m∑d(v;)≥k+2(n-k) 由m=n-1,将此结果代入上式后解得k≥2
定理： 设T是n阶非平凡的无向树，则T中 至少有两片树叶。 证 : 因为T是非平凡树,所以T中每个顶点的度 数都大于等于1, 设T有k片树叶, 则有(n-k) 个顶点度数大于等于2,由握手定理可知 2m=∑d(vi ) ≥ k+2(n-k) 由m=n-1,将此结果代入上式后解得 k ≥ 2
例:画出5阶所有非同构的无向树。 解:设T为5阶无向树则T的边数为4,T的度 序列之和为8,4(T)≤4,δ(T心1,可能的度序 列为: (1)1,1,1,1,4;(2)1,1,1,2,3;(3)1,1,2,2,2: +r
例：画出5阶所有非同构的无向树。 解：设Ti为5阶无向树,则Ti的边数为4， Ti的度 序列之和为8， △(Ti )≤4, (Ti )≥1, 可能的度序 列为： (1) 1,1,1,1,4; (2) 1,1,1,2,3; (3) 1,1,2,2,2; 。 。 。 。 。 。 。 。 。 。 。 。 。 。