●6,例112证明:设G是有n个顶点的简单图,且 627-2,则k(G=δ。 ●证明方法:分面治之 证明: 当δ-付时G=Kn,所以kG)=6 当δ=7-2时,若顶点v1v2不相邻,则对任意第3 个顶点v,G中有边{vnV3,{2v3}此时对任意n-3 个顶点构成的子集V,均有GV连通(在G中删去 任意n-3个顶点依然连通)。所以kG-2=δ。由定 理81,(G)s6,即得k(G)=δ
6，例11.2 证明：设G是有n个顶点的简单图，且 n-2，则k(G)=。 证明方法：分而治之。 证明： 当=n-1时G=Kn，所以k(G)=。 当=n-2时，若顶点v1, v2不相邻，则对任意第3 个顶点v3， G中有边{v1,v3}, {v2,v3}。此时对任意n-3 个顶点构成的子集V’，均有G-V’连通（在G中删去 任意n-3个顶点依然连通）。所以k(G)n-2=。由定 理8.1，(G)，即得k(G)=
●6,定义114(k连通的) ●若图G的k(G)≥k,称G为k连通的
6，定义11.4（ k-连通的） 若图G的k(G)k，称G为k-连通的
●7,定义11.5(k边连通的) ●若图G的(G)≥k,称G为k边连通的
7，定义11.5（ k-边连通的） 若图G的(G)k，称G为k-边连通的
二、割点与块 ●1,定理11.2 ●设v是连通图G的一个顶点,下列论断是 等价的: ●(1)是G的一个割点 ●(2)对于顶点v,存在两个不同的顶点u和 W,使顶点v在每一条从u到W的路上。 ●(3)存在W的一个分成U和W的划分 使对任意两顶点u∈U和W∈W,顶点ⅵ 每一条从u到W的路上
二、割点与块 1，定理11.2 设 v是连通图 G的一个顶点，下列论断是 等价的： (1) v是 G的一个割点。 (2)对于顶点 v，存在两个不同的顶点 u 和 w，使顶点 v在每一条从 u 到 w的路上。 (3)存在V-{v}的一个分成 U 和 W的划分， 使对任意两顶点 u U 和 w W，顶点 v在 每一条从 u 到 w的路上
●证明方法: ●(1)→(3) ●(3)→(2) (2)→(1 ●/参考定理10.1证明
证明方法： (1)(3) (3)(2) (2)(1) /* 参考定理10.1证明 */