2、连通度的性质 定理1（惠特尼1932）对任意图G,有： k(G)≤(G)≤6(G) 证明：(1)先证明λ(G)至δ(G) 最小度顶点的关联集作成G的分离集，所以：(G)≤δ(G)。 (2)再证明k(G)≤λ(G) 由定义，k(G)≤n-1。考虑最小边割集 [S,S] [S,S] S
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 2、连通度的性质 定理1 (惠特尼1932) 对任意图G，有： kG G G () () () 证明： (1) 先证明λ(G)≦δ(G) 最小度顶点的关联集作成G的分离集，所以： λ(G)≦δ(G)。 (2) 再证明 k (G)≦ λ(G) 由定义，k (G) ≦n -1。考虑最小边割集 [, ] S S S S [, ] S S G
情形1 S中点与S中点均连接 [S,S] 则有： [s,s]=l小S≥n-1≥kG) 所以有：k(G)≤(G。 情形2 S中点与S中点不都连接 在这种情形下，取x∈S,y∈S,且x与y不邻接 8
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 情形1 则有： S S [, ] S S G S S 中点与 中点均连接 SS S S n kG , 1 () 所以有： k (G)≦ λ(G)。 情形2 S S 中点与 中点不都连接 在这种情形下，取 x Sy S x y , ，且 与 不邻接
令： 7={ykad,且veS}:{ulu≠x,u∈S,且u在S中有邻点 于是，G中任意一条（区，y)路必然经过T中一些点，所以，T 为G的一个点分离集。 在G中取如下边集： E,={xp∈S;{从T4S每个顶点取一条到S的边
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 令： T v xadjv v S u u x u S u S , ,, 且 且 在 中有邻点 U 于是，G中任意一条(x, y)路必然经过T中一些点, 所以，T 为G的一个点分离集。 S S G T T x T T T y 在G中取如下边集： E xv v S T S 1 U I 从 每个顶点取一条到 S的边
S 则： ll= 所以： (G)=[S,S]≥E=T≥k(G) 注：(I)定理中严格不等式能够成立。 G k(G)=1,λ(G)=2,δ(G)=3 10
0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 则： S S G T T x T T T y 所以： E1 = T 1 ( ) [, ] ( ) G SS E T kG 注： (1) 定理中严格不等式能够成立。 k (G)=1 , λ(G)=2 ,δ(G)=3 G