U(G1)-1+d2(l)≤k’≤d(G)≤U(G1)-1+d2(l) 可见x'=δ(G)。证毕。 推论222设非空简单图G中任二不相邻顶点和v都满足d(a)+d(v)≥b-1,则 k(G)=o(G)。 证明:若G中任意两点都相邻,则G是完全图,k(G)=U-1=6(G),结论成立。若G 中有不相邻顶点,则 diam G≥2但由于任二不相邻顶点和v都满足d(a)+d(v)≥b-1, 即任二不相邻顶点u和y都有公共的邻点。因此又有 diam G≤2。从而 diam C=2。由定 理224便得'(G)=6(G)。证毕 按照推论222,下面的结论是显然的。 推论223设G是一个简单图,若O(G)≥ 2,则x'(G)=(G)。 虽然直径为2的图能使得边连通度达到上界,但其点连通度仍然可能很小。例如下图的 直径为2,其连通度只有1。 §232连通图的性质 定义231无割点的连通图称为一个块bock)设G是一个图,H是G的一个子图,若H 本身是一个块且它是G中具有此性质的极大子图,则称H是图G的一个块 下面是块及图的块的例子。 块 含4个块的图 注:至少有三个顶点的图是块当且仅当它是2一连通图。(若只有两个顶点,则有反例,例 如K2是个块,但不是2连通的。) 关于2连通图(块),有下列重要结论 定理23.1( Whitney,1932)v≥3的图G是2一连通图(块)当且仅当G中任二顶点共圈。 证明:充分性:设G中任二顶点在同一圈上,欲证G是2一连通的。 对vw∈(G),任取u,v∈V(G-w)。由条件,u,v在G中共处于某个圈C上。若 v∈C,则在G\w中u,v仍在圈C上:若w∈C,则G-w中t,v在路C-w上。总之 u,y在G-w中有路相连。由,v的任意性,G-w是连通图,故w不是G的割点。再由w 的任意性知,G无割点,即G是2一连通的
6 1 20 υ( )1 () G du −+ ≤ κ′ ≤ δ (G) ≤ 1 20 υ( )1 () G du − + 可见κ δ ′ = (G) 。证毕。 推论 2.2.2 设非空简单图 G 中任二不相邻顶点 u 和 v 都满足 du dv () () 1 + ≥ − υ ，则 κ δ ′(G) (G) = 。 证明：若 G 中任意两点都相邻，则 G 是完全图，κ′(G) 1 (G) = υ δ − = ，结论成立。若 G 中有不相邻顶点，则diam 2 G ≥ 。但由于任二不相邻顶点u和v都满足 du dv () () 1 + ≥− υ ， 即任二不相邻顶点 u 和 v 都有公共的邻点。因此又有diam 2 G ≤ 。从而diam 2 G = 。由定 理 2.2.4 便得κ δ ′(G) (G) = 。证毕。 按照推论 2.2.2，下面的结论是显然的。 推论 2.2.3 设 G 是一个简单图，若 1 ( ) 2 G υ δ − ≥ ，则κ ′(G) (G) = δ 。 虽然直径为 2 的图能使得边连通度达到上界，但其点连通度仍然可能很小。例如下图的 直径为 2，其连通度只有 1。 §2.3 2-连通图的性质 定义 2.3.1 无割点的连通图称为一个块(block)。设 G 是一个图，H 是 G 的一个子图，若 H 本身是一个块且它是 G 中具有此性质的极大子图，则称 H 是图 G 的一个块。 下面是块及图的块的例子。 块 含 4 个块的图 注：至少有三个顶点的图是块当且仅当它是 2－连通图。（若只有两个顶点，则有反例，例 如 K2 是个块，但不是 2 连通的。） 关于 2 连通图（块），有下列重要结论。 定理 2.3.1 (Whitney,1932) ν ≥ 3的图 G 是 2－连通图（块）当且仅当 G 中任二顶点共圈。 证明：充分性：设 G 中任二顶点在同一圈上，欲证 G 是 2－连通的。 对∀w∈V(G) ，任取u, v ∈V(G − w) 。由条件，u, v 在 G 中共处于某个圈 C 上。若 w ∉C ，则在G \ w 中 u, v 仍在圈 C 上；若 w ∈C ，则G − w中 u, v 在路C − w 上。总之 u, v 在G − w中有路相连。由 u, v 的任意性，G − w是连通图，故 w 不是 G 的割点。再由 w 的任意性知，G 无割点，即 G 是 2－连通的
必要性:设G是2一连通图,欲证任二顶点L,v都在同一圈上。 对距离d(l,v)作归纳法。 d(l,)=1时,因x≥K≥2,故G中无割边,G-仍连通。因此G-中存在 条(u,v)路P。这表明在G中a,v都在圈P+上。 假定d(l,v)<k时,结论成立。下证d(u,v)=k时结论也成立。 当d(l,v)=k时,设f=l…wv是长为k的一条(u,v)路,则d(l,)=k-1。由归 纳法假设,l,w在同一圈上,故在t,w间有两条无公共内部顶点的路P和Q。因G是2连 通图,故G-仍连通。在G-中存在(,v)路P。令x是P上最后一个与PUQ的公 共顶点(因l∈P∪Q,这样的x存在)。不妨设x∈P,则P上(,x)段+P'上(x,v)段 与Q+w是两条内部无公共点的(,v)路。故,v在同一圈上。归纳法完成。证毕 推论23.1v≥3的图G是2连通图(块)当且仅当G中任二顶点被至少两条内部无公共顶 点的路所连 推论23.,2若v≥3的图G是2连通图(块),则G的任二边都位于同一圈上。 证明:设G是v≥3的2连通图,且e1e2∈E(G),在e1和e2上各添加一个新的顶点v1和 V2,构成一个新图G’。G’仍是2连通的。由 Whitney定理,v1和v2在G中位于同一个圈 上。故e1和e2在G中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理23.2设G是v≥3的连通图,则下列命题等价 (1)G是2连通的(块) (2)G的任二顶点共圈 (3)G的任一顶点与任一边共圈 (4)G的任二边共圈; (5)对vu,v∈(G)及ve∈E(G),存在(u,v)路含有边e; (6)对vu,v,w∈F(G),存在(l,v)路含有顶点w (7)对vu,v,w∈F(G),存在(l,v)路不含有顶点v。 证明:(1)→(2)见 Whitney定理 (2)→(3)设G中任二顶点共圈。对veV(G)及ve=xy∈E(G),若x=或y=l, 则结论显然。以下假定x,y≠l。设C是含u与x的圈。若y∈C,则C上含有u的(x,y)
7 必要性：设 G 是 2－连通图，欲证任二顶点 u, v 都在同一圈上。 对距离d(u, v) 作归纳法。 d(u, v) = 1时，因κ ′ ≥ κ ≥ 2 ，故 G 中无割边，G − uv 仍连通。因此G − uv 中存在 一条(u, v) 路 P1 。这表明在 G 中 u, v 都在圈 P + uv 1 上。 假定d(u, v) < k 时，结论成立。下证d(u, v) = k 时结论也成立。 当d(u, v) = k 时，设 P = u"wv 0 是长为 k 的一条(u, v) 路，则d(u,w) = k −1。由归 纳法假设，u, w 在同一圈上，故在 u, w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连 通图，故G − w仍连通。在G − w中存在(u, v) 路 P′ 。令 x 是 P′ 上最后一个与 P ∪ Q 的公 共顶点（因u ∈ P ∪ Q ，这样的 x 存在）。不妨设 x ∈ P ，则 P 上(u, x)段＋ P′ 上(x, v) 段 与Q + wv 是两条内部无公共点的(u, v) 路。故 u, v 在同一圈上。归纳法完成。证毕。 推论 2.3.1 ν ≥ 3的图 G 是 2 连通图（块）当且仅当 G 中任二顶点被至少两条内部无公共顶 点的路所连。 推论 2.3.2 若ν ≥ 3的图 G 是 2 连通图（块），则 G 的任二边都位于同一圈上。 证明：设 G 是ν ≥ 3的 2 连通图，且 , ( ) e1 e2 ∈ E G ，在 1 e 和 2 e 上各添加一个新的顶点 1 v 和 2 v ，构成一个新图G′。G′仍是 2 连通的。由 Whitney 定理， 1 v 和 2 v 在G′中位于同一个圈 上。故 1 e 和 2 e 在 G 中位于同一个圈上。证毕。 关于块的部分等价命题总结在下一个定理中。 定理 2.3.2 设 G 是ν ≥ 3的连通图，则下列命题等价： （1） G 是 2 连通的（块）； （2） G 的任二顶点共圈； （3） G 的任一顶点与任一边共圈； （4） G 的任二边共圈； （5） 对∀u, v ∈V(G) 及∀e ∈ E(G) ，存在(u, v)路含有边 e； （6） 对∀u, v,w∈V(G) ，存在(u, v)路含有顶点 w; （7） 对∀u, v,w∈V(G) ，存在(u, v)路不含有顶点 w。 证明：（1）⇒（2）见 Whitney 定理。 （2）⇒（3）设 G 中任二顶点共圈。对∀u ∈V(G) 及∀e = xy ∈ E(G)，若 x = u 或 y = u ， 则结论显然。以下假定 x, y ≠ u 。设 C 是含 u 与 x 的圈。若 y ∈C ，则 C 上含有 u 的(x, y) P P0 u P´ v Q x w