第9章树 ②由(1)可得(2) 再证反证法,若图7不连通,设有k个连通分支T1, 72,…,T(心2),其顶点数分别为n1,n2,…,nk, 则有 ∑ 边数分别为m1,m2,…,mk,则有 ∑m
第9章 树 ②由（1）可得（2）。 再证反证法，若图T不连通，设T有k个连通分支T1， T2，…，Tk（k≥2），其顶点数分别为n1，n2，…，nk， 则有 1 k i i n n = = 边数分别为m1，m2，…，mk，则有 1 k i i m m = =
第9章树 因此,有 k ∑m=∑(n1-1)=n-k<n 即m<n-1,这与m=n-1矛盾,故T是连通的m=n-1图
第9章 树 因此，有 1 1 ( 1) 1 k k i i i i m m n n k n = = = = − = − − 即m＜n-1，这与m=n-1矛盾，故T是连通的m=n-1图
第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
第9章树 删去vo及其关联的边,得到图T,由假设知T无回 路,现将v及其关联的边再加到T,则还原成T,所以T 没有回路。 如果在连通图7中增加一条新边(,v),则(v, )与P中从v到v的一条初级路径构成一个初级回路, 且该回路必定是唯一的,否则当删去新边(v,v)时, T中必有回路,产生矛盾
第9章 树 删去v0及其关联的边，得到图T′ ，由假设知T′无回 路，现将v0及其关联的边再加到T′ ，则还原成T，所以T 没有回路。 如果在连通图T中增加一条新边（vi，vj），则（vi， vj）与T中从vi到vj的一条初级路径构成一个初级回路， 且该回路必定是唯一的，否则当删去新边（vi，vj）时， T中必有回路，产生矛盾
第9章树 ④由(3)可得(4)。 若图7不连通,则存在两个顶点v;和v,在v;,v;之 间没有路径,如果增加边(ν,ν;)不产生回路,这与 (3)矛盾,因此T连通。因为T中无回路,所以删去任 意一条边,图必不连通。故图中每一条边均是桥。 ⑤由(4)可得(5) 由图的连通性可知,任意两个顶点之间都有一条 通路,是初级通路。如果这条初级通路不唯一,则T中 必有回路,删去回路上的任意一条边,图仍连通,与 (4)矛盾。故任意两个顶点之间有唯一一条初级回路
第9章 树 ④由（3）可得（4）。 若图T不连通，则存在两个顶点vi和vj，在vi，vj之 间没有路径，如果增加边（vi，vj）不产生回路，这与 （3）矛盾，因此T连通。因为T中无回路，所以删去任 意一条边，图必不连通。故图中每一条边均是桥。 ⑤由（4）可得（5）。 由图的连通性可知，任意两个顶点之间都有一条 通路，是初级通路。如果这条初级通路不唯一，则T中 必有回路，删去回路上的任意一条边，图仍连通，与 （4）矛盾。故任意两个顶点之间有唯一一条初级回路