第9章树 ③由(2)可得(3) 若T是连通图并有n-1条边。施归纳于顶点数n 当n=2时,m=n-1=1,所以没有回路,如果增加 条边,只能得到唯一的一个回路。 假设n=时,命题成立。则当n=k+1时,因为T是连 通的并有n-1条边,所以每个顶点都有d(ν)≥1,并且 至少有一个顶点v,满足d(v)=1。否则,如果每个 顶点ν都有d(p)≥2,那么必然会有总度数2m≥2n,即 mn,这与条件m=m-1矛盾。因此至少有一个顶点v, 满足d(V)=1第9章 树 ③ 由（2）可得（3）。 若T是连通图并有n-1条边。施归纳于顶点数n。 当n=2时，m=n-1=1，所以没有回路，如果增加一 条边，只能得到唯一的一个回路。 假设n=k时，命题成立。则当n=k+1时，因为T是连 通的并有n-1条边，所以每个顶点都有d（v）≥1，并且 至少有一个顶点v0，满足d（v0）=1。否则，如果每个 顶点v都有d（v）≥2，那么必然会有总度数2m≥2n，即 m≥n，这与条件m=n-1矛盾。因此至少有一个顶点v0， 满足d（v0）=1