2、连通度的性质 定理1（惠特尼1932）对任意图G,有： k(G)≤(G)≤δ(G) 证明：(1)先证明λ(G)≤δ(G) 最小度顶点的关联集作成G的断集，所以：(G)δ(G)。 (2)再证明k(G)≤λ(G) 由定义，k(G)≤n-1。考虑最小边割集[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 6 2、连通度的性质 定理1 (惠特尼1932) 对任意图G，有： k G G G ( ) ( ) ( ) 证明： (1) 先证明λ(G)≦δ(G) 最小度顶点的关联集作成G的断集，所以：λ(G)≦δ(G)。 (2) 再证明 k (G)≦ λ(G) 由定义，k (G) ≦n -1。考虑最小边割集 [ , ] S S S S [ , ] S SG
情形1S中点与S中点均连接 [S,S] 则有： [S,s]=|sS≥n-1≥k(G) 所以有：k(G)≤(G。 情形2 S中点与S中点不都连接 在这种情形下，取x∈S,y∈S,且x与y不邻接
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 情形1 则有： S S [ , ] S S G S S 中点与 中点均连接 S S S S n k G , 1 ( ) = − 所以有： k (G)≦ λ(G)。 情形2 S S 中点与 中点不都连接 在这种情形下，取 x S y S x y , ，且 与 不邻接
令 T={vxadjiv,.且veSU{uu≠x,u∈S,且u在S中有邻点} S 于是，G中任意一条K,y)路必然经过T中一些点，所以，T 为G的一个点分离集。 在G中取如下边集： E,={xvv∈U{从T∩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 8 令： T v xadjv v S u u x u S u S = , , , 且 且 在 中有邻点 于是，G中任意一条(x, y)路必然经过T中一些点, 所以，T 为G的一个点分离集。 S S G T T x T T T y 在G中取如下边集： E xv v S T S 1 = 从 每个顶点取一条到S的边
则：E=可 所以： 2(G)=[S,S]≥E=|T≥k(G) 注：(1定理中严格不等式能够成立。 G k(G)=1,λ(G)=2,6(G)=3
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 则： S S G T T x T T T y 所以： E1 = T 1 ( ) [ , ] ( ) G S S E T k G = = 注： (1) 定理中严格不等式能够成立。 k (G)=1 , λ(G)=2 ,δ(G)=3 G