中科院研究生院专业基础课：《图论与网络流理论》第二章图的连通性（高随祥）.pdf_大学文库

1 第二章图的连通性在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图 G1，删除一条边或一个顶点便可使其变得不连通；而对于图 G2，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图 G3，要破坏其连通性，则至少需要删除三条边或三个顶点。本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画 1 连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的 2 连通和 k 连通性。 §2.1 割点和割边定义 2.1.1 设v ∈V (G) ，如果 w(G − v) > w(G) ，则称 v 为 G 的一个割点。（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别）。例如，下图中 u, v 两点是其割点。定理 2.1.1 如果点 v 是简单图 G 的一个割点，则边集 E(G)可划分为两个非空子集 E1和 E2 ，使得 [ ] G E1 和 [ ] G E2 恰好有一个公共顶点 v。证明留作习题。推论 2.1.1 对连通图 G，顶点 v 是 G 的割点当且仅当G − v 不连通。定理 2.1.2 设 v 是树 T 的顶点，则 v 是 T 的割点当且仅当d(v) > 1。证明：必要性：设 v 是 T 的割点，下面用反证法证明d(v) > 1。若d(v) = 0 ，则T ≅ K1，显然v 不是割点。若d(v) = 1，则T − v 是有ν (T − v) −1条边的无圈图，故是树。从而 w(T − v) = 1 = w(T ) 。因此v 不是割点。以上均与条件矛盾。充分性：设d(v) > 1，则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条(u,w) 路。因 T 是树， uvw 是 T 中唯一的(u,w) 路，从而 w(T − v) > 1 = w(T ) 。故v 是割点。证毕。 G1 G2 G3 u v

2 推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。证明：设 T 是 G 的生成树，则 T 至少有两个叶子 u,v，由上一定理知，u,v 都不是 T 的割点，即 w(T − u) = w(T ) = 1。由于T − u 是图G − u 的生成树，故 w(G − u) = w(T − u) = w(T ) = 1 = w(G) ，因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。定理 2.1.3 设 v 是连通图 G 的一个顶点，则下列命题等价：（1） v 是 G 的割点；（2）存在u,w∈V(G) ，使得u,w ≠ v 且 v 在每条(u,w) 路上；（3）存在V (G) \ {v}的一个划分：V (G) \ {v} = U ∪W ，U ∩W = φ ，使得对∀u ∈U 和∀w ∈W ，v 在每条(u,w) 路上。证明：（1）⇒（3）因 v 是割点，故G − v 至少有两个连通分支G1 、G2 。令 ( ) U = V G1 而 ( ) \ ( ( ) { }) 1 W = V G V G ∪ v ，则对∀u ∈U 和∀w ∈W ，u、w 分别属于G − v 的不同的连通分支。可见 G 中所有的(u,w) 路必经过 v（否则G − v 中仍有(u,w) 路，这与 u、w 分别属于G − v 的不同的连通分支矛盾）。（3）⇒（2）显然。（2）⇒（1）若 v 在每条(u,w) 路上，则G − v 中不存在(u,w) 路，即G − v 不连通，故 v 是 G 的割点。证毕。定义 2.1.2 设e ∈ E(G)，如果 w(G − e) > w(G) ，则称 e 为 G 的一条割边。例如下图中，边 uv，边 wu 都是其割边。定理 2.1.4 边 e 是 G 的割边当且仅当 e 不在 G 的任何圈中。证明：证其逆否命题：e 不是割边当且仅当 e 含在 G 的某个圈中。必要性：设 e = xy 不是割边。假定 e 位于 G 的某个连通分支G1 中，则G − e 1 仍连通。故在 G − e 1 中有(x, y)路 P，P + e 便构成G1 中一个含有 e 的圈。充分性：设 e 含在 G 的某个圈 C 中，而 C 含于某连通分支G1 中，则G − e 1 仍连通。故 w(G − e) = w(G) ，这说明 e 不是割边。证毕。定理 2.1.5 一个连通图是树当且仅当它的每条边都是割边。证明：连通图 G 是树⇔G 无圈⇔任何边 e 不含在圈中⇔任何边 e 是 G 的割边。证毕。 u v w

3 定理 2.1.6 设 e 是连通图 G 的一条边，则下列命题等价：（1） e 是 G 的割边；（2） e 不在 G 的任何圈上；（3）存在u, v ∈V (G) ，使得 e 在每条(u, v)路上；（4）存在V (G) 的一个划分：V(G) = U ∪W ，U ∩W = φ ，使得对∀u ∈U 和∀w ∈W ， e 在每条(u,w) 路上。证明：（1）⇔（2）定理 2.1.4 已证。（1）⇒（4）⇒（3）⇒（1）的证明与定理 2.1.3 的证明类似。 §2.2 连通度和边连通度定义 2.2.1 对图 G，若 V(G)的子集V ′使得 w(G −V ′) > w(G) ，则称V ′为图 G 的一个顶点割集。含有 k 个顶点的顶点割集称为 k－顶点割集。注：（1）割点是 1－顶点割集。（2）完全图没有顶点割集。定义 2.2.2 图 G 的连通度定义为κ ( ) min{| || G VV = ′ ′是连通图 G 的顶点割集}。特别地，完全图的连通度定义为κ(Kν ) =ν −1, 空图的连通度定义为 0, 不连通图的连通度定义为 0。注：(1) 若 G 是平凡图，则κ (G) = 0。 (2) 使得|V ′ |= κ (G) 的顶点割集V ′称为 G 的最小顶点割集。 (3) 若κ (G) ≥ k ，则称 G 为 k 连通的。 (4) 按上述定义，图 G 是 k 连通的，当且仅当 G 的最小点割集至少含 k 个顶点，当且仅当 G 中没有 k−1 点割集，当且仅当从 G 中任意去掉 k−1 个顶点后，所剩图仍连通。 (5) 按照 k 连通的定义，若图 G 是 k 连通的，则它也是 k−1 连通、k−2 连通、…、1 连通的。因此，所有非平凡连通图都是 1 连通的。定义 2.2.3 对图 G，若 E(G)的子集 E′使得 w(G − E′) > w(G) ，则称 E′为图 G 的一个边割集。含有 k 条边的边割集称为 k－边割集。注：(1) 对非平凡图 G，若 E′是一个边割集，则G \ E′ 不连通。 (2) 一条割边构成一个 1－边割集。 (3) 设 S ⊂ V(G) ，S′ ⊂ V(G) ，S, S′ ≠ φ ，记号[S, S′] 表示一端在 S 中另一端在 S′ 中的所有边的集合。对图 G 的每个边割集 E′，必存在非空的 S ⊂ V (G) ，使得[S, S ] 是 G 的一个边割集，其中 S = V \ S 。定义 2.2.4 图 G 的边连通度定义为κ′( ) min{| || G EE = ′ ′是连通图 G 的边割集}。完全图的边连通度定义为κ′(Kν ) =ν −1，空图的边连通度定义为 0，不连通图的边连通度定义为 0。注：(1) 对平凡图 G，κ′(G) = 0。 (2) 是含有割边的连通图，则κ′(G) = 1

4 (3) 使得| E′ |= κ ′(G) 的边割集 E′称为 G 的最小边割集。 (4) 若κ′(G) ≥ k ，则称 G 为 k 边连通的。 (5) 按上述定义，图 G 是 k 边连通的，当且仅当 G 的最小边割集至少含 k 条边，当且仅当 G 中没有 k−1 边割集，当且仅当从 G 中任意去掉 k−1 条边后，所剩图仍连通。 (6) 按照 k 边连通的定义，若图 G 是 k 边连通的，则它也是 k−1 边连通、k−2 边连通、…、 1 边连通的。因此，所有非平凡连通图都是 1 边连通的。例如，下列图中，G1 是连通的且有割点和割边，因此是 1 连通的和 1 边连通的；G2的最小点割集含 1 个点，最小边割集含 2 条边，故它是 1 连通的和 2 边连通的；G3的最小点割集和最小边割集分别含 2 个点和 2 条边，因此是 2 连通的和 2 边连通的；G4的最小点割集和最小边割集分别含 3 个点和 3 条边，因此是 3 连通的和 3 边连通的。定理 2.2.1 κ (G) ≤ κ ′(G) ≤ δ (G) 。证明：先证κ (G) ≤ κ′(G) 。对图的边连通度κ ′( ) G 作数学归纳法。对κ′( ) G ＝1 的图 G，若G K = 2 ，则显然κ′() 11 G = υ − = ；若G K ≠ 2 ，则 G 至少含三个点。设 e = uv 是 G 的一条割边，则 u 或 v 必是割点，故κ ( ) G =1。总之，此时κ ( ) G =κ′( ) G ＝1。假设对所有κ ′ = k 的图，都有κ κ ′ ≤ ，则对κ ′() 1 G k = + 的图G，设E是它的一个k + 1 边割集。任取边e uv E G = ∈ ( ) ，则 E e − 是G e − 的最小边割集，故κ′( ) Ge k − = 。由归纳假设，κ κ ( )( ) Ge Ge −≤ − ′ 。取G e − 的最小点割集 T，则 || ( ) ( ) T Ge Ge k = −≤ −= κ κ′ ，且T u ∪{ }构成 G 的最小点割集。故κ ( ) | { }| | | 1 1 ( ) GTuT k G = ∪ ≤ +≤ + = κ′ 。归纳完成。再证κ′(G) ≤ δ (G) 。设d(v) = δ 。删去与 v 关联的δ 条边后，G 变成不连通图，故这δ 条边构成 G 的一个边割集。因此κ′(G) ≤ δ (G) 。证毕。下图 G1 是一个κ = = 2, 3 κ′ 和δ = 4 的图，G2 是一个κ = 1, 2 κ′ = 和δ = 3的图。 G1 G2 G3 G4 G1 G2

5 定理 2.2.2 对具有υ 个顶点ε 条边的连通图 G，有 2 ( ) G ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。证明：因 ( ) 2 () vVG ε d v δυ ∈ = ≥ ∑ ，故 2ε δ υ ≤ ，由定理 2.2.1， 2ε κ δ υ ≤ ≤ 。由于κ 是整数，因此 2ε κ ν ⎢ ⎥ ≤ ⎢ ⎥ ⎣ ⎦ 。证毕。定理 2.2.3 设 G 是一个简单图，k 是一个自然数，若 2 ( ) 2 k G υ δ + − ≥ ，则 G 是 k 连通的。证明：用反证法。假如 G 不是 k 连通的，则 G 的连通度κ < k ，即存在 G 的点割集 S，使得| | S k < ，且 G−S 不连通。因 G −S 有υ− |S|个顶点，且至少有两个连通分支，故必有 G−S 的某个连通分支G′含有不超过 |S| 2 υ− 个顶点。注意到G′中任一个顶点只可能与G′内的点及 S 中的点相邻，因而其在 G 中的顶点度 | | |S| 2 1| | 2 2 S S υ− υ+ − ≤ −+ = 。结合| | S k < ，这意味着δ (G) ≤ | |2 2 2 2 υ+ S k − +− υ < ，与定理条件矛盾。证毕。推论 2.2.1 设 G 是一个简单图，若 1 ( ) 2 G υ δ − ≥ ，则 G 是连通的。定理 2.2.4 设 G 是一个直径为 2 的简单图，则κ′(G) (G) = δ 。证明：设 S 是 G 的一个最小边割集，则 G−S 有多于一个连通分支，取其中顶点数最少的一个记为 G1，G−S 的其余部分记为 G2。如果 G1 中存在顶点 u，它在 G 中不与 G2 的顶点相邻，则对，由 (,) 2 G d uv = 知，在 G 中 v 有属于 G1 的邻点。由此可知，在 G 中来看，要么 G1 中每个点都在 G2 中有邻点，要么 G2 中每个点都在 G1 中有邻点。在前一种情况下， 1 | S | (G ) ≥ υ ，在后一种情况下， 2 | S | (G ) ≥ υ 。总之， 12 1 κ υυ υ ′ =≥ = | S | min{ (G ), (G )} (G ) 。（1）对 1 ∀ ∈u G ，用 1 d u( ) 和 1 d u( ) 分别表示在 G 中 u 与 G1和 G2 连的边数。则 12 1 2 ( ) () () () ( ) 1 () G d u du du G du G δ ≤ = + ≤ −+ υ 。根据定理 2.2.1， κ δ ′ ≤ ≤ (G) 1 2 υ( ) 1 () G du − + 。（2）结合（1）式可得 2 d u() 1 ≥ 。任取 0 1 u VG ∈ ( ) ，由于 1 10 2 2 20 1 20 | | () () ( ) ( ) 1 ( ) uG uG u κ υ S du du du G du ∈ ∈− ′ = = = + ≥ −+ ∑ ∑ ，结合（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－连通的

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

(6)→(7):对V,v,w∈V(G),存在(u,)路P含有顶点v,则P的从u到v的一段不含有w (7)→(1):因为对vw∈(G)及va,v∈F(G),存在(u,v)路不含有顶点w,故w不是割点。由w的任意性,G无割点。从而G是块。证毕 §24 Menger定理上节的 Whitney定理表明,对一个图G,G的最小点割集含至少2个点当且仅当G 中任意两点间都有至少2条内部点不交的路,即“分离”G中任意两点所需删除的最少顶点数和这两点间内部点不交路的最大条数要么都大于等于2,要么都不超过2。这涉及到图的连通性能的两个度量:删除顶点时图保持连通的能力和顶点间不交路径的重数。 Whitney定理说明对2连通图这两种连通性度量是等价的。下列 Menger定理显示,这一结论对任意k 连通图都成立。设G是一个简单图,x,y是G中任二不同顶点。如果从G中删去一组顶点后不再有 (x,y)路则称这组顶点分离x和y,而称这组顶点为一个(x,y)分离集。G中含点数最少的(x,y) 分离集称为最小x,y)分高集,其顶点数称为G的(x,y分高数,记为s(x,y)。此外,将G中两两内部点不交的(x,y)路的最大条数记为r(x,y) 定理241( Menger,1927)对任意图G,设x,y是G中两个不相邻顶点,则G中分离x,y 所需的最少顶点数等于G中两两内部点不交的(x,y)路的最大条数,即s(x,y)=r(x,y) 证明:首先,对任意图G和G中任意两个不相邻顶点x,y,显然有sx,y)≥r(x,y)。下面用反证法证明对任意图G和G中任意两个不相邻顶点x,y,s(x,y)≤r(x,y) 假设结论不真。则存在图G和G中两个不相邻顶点x,y,使得s(x,y)>r(x,y)。取G为具有这种性质的所有图中顶点数最少并且边数最少的一个,即:对具有上述性质的任何一个图H,要么D(G)rx,y)≥0,可知G是连通图。如果s(x,y)=1,则必须r(x,y)=0,这与G是连通图矛盾。因此sx,y)>1。 (2)对G的任二异于x,y的相邻顶点u和v,存在G的顶点子集U,满足|U=s(x,y)-1 且UU{础}和UU{v}都是G的(x,y)分离集。事实上,设e=l,H=G-e。H的(x,y)分离数 SH(x,y)≥s(x,y)-1,(* (否则存在H的(x,y)分离集R使得|Rsx,y)-2,则RU{}是G的(x,y)分离集,且只含 s(x,y)-1个点,这与G的(x,y)分离数为sx,y)矛盾)。另一方面,由于s(x,y)>r(x,y),H中两两内部点不交的(x,y)路的条数 n(x,y)≤r(x,y)≤s(x,y)-1。(*)

9 （6）⇒（7）：对∀u, v,w∈V(G) ，存在(u,w) 路 P 含有顶点 v，则 P 的从 u 到 v 的一段不含有 w。（7）⇒（1）：因为对∀w∈V(G) 及∀u, v ∈V(G) ，存在(u, v)路不含有顶点 w，故 w 不是割点。由 w 的任意性，G 无割点。从而 G 是块。证毕。 §2.4 Menger 定理上节的 Whitney 定理表明，对一个图 G，G 的最小点割集含至少 2 个点当且仅当 G 中任意两点间都有至少 2 条内部点不交的路，即“分离”G 中任意两点所需删除的最少顶点数和这两点间内部点不交路的最大条数要么都大于等于 2，要么都不超过 2。这涉及到图的连通性能的两个度量：删除顶点时图保持连通的能力和顶点间不交路径的重数。Whitney 定理说明对 2 连通图这两种连通性度量是等价的。下列 Menger 定理显示，这一结论对任意 k 连通图都成立。设 G 是一个简单图，x, y 是 G 中任二不同顶点。如果从 G 中删去一组顶点后不再有 (x, y)路则称这组顶点分离 x 和 y，而称这组顶点为一个(x, y)分离集。G 中含点数最少的(x, y) 分离集称为最小(x, y)分离集，其顶点数称为 G 的(x, y)分离数，记为 s(x, y)。此外，将 G 中两两内部点不交的(x, y)路的最大条数记为 r(x, y)。定理 2.4.1（Menger, 1927）对任意图 G，设 x, y 是 G 中两个不相邻顶点，则 G 中分离 x, y 所需的最少顶点数等于 G 中两两内部点不交的(x, y)路的最大条数，即 s(x, y) = r(x, y)。证明：首先，对任意图 G 和 G 中任意两个不相邻顶点 x, y，显然有 s(x, y)≥ r(x, y) 。下面用反证法证明对任意图 G 和 G 中任意两个不相邻顶点 x, y，s(x, y) ≤ r(x, y)。假设结论不真。则存在图 G 和 G 中两个不相邻顶点 x, y，使得 s(x, y) > r(x, y)。取 G 为具有这种性质的所有图中顶点数最少并且边数最少的一个，即：对具有上述性质的任何一个图 H，要么υ(G) (H) r(x, y) ≥ 0，可知 G 是连通图。如果 s(x, y)=1，则必须 r(x, y)=0,这与 G 是连通图矛盾。因此 s(x, y) > 1。（2）对G的任二异于x, y的相邻顶点u和v，存在G的顶点子集U，满足|U| ( , ) 1 = − sxy 且 U {} ∪ u 和 U {} ∪ v 都是 G 的(x, y)分离集。事实上，设 e = uv，H = G − e。H 的(x, y)分离数 sH (x, y) ≥ s(x, y) −1， (∗) （否则存在 H 的(x, y)分离集 R 使得|R|≤ s(x, y) −2，则 R {} ∪ u 是 G 的(x, y)分离集，且只含 s(x, y) −1 个点，这与 G 的(x, y)分离数为 s(x, y)矛盾）。另一方面，由于 s(x, y) > r (x, y)，H 中两两内部点不交的(x, y)路的条数 (, ) Hr xy ≤ r (x, y)≤ s(x, y) −1。(∗∗)

10 由 G 的最小性可知，H 中的(x, y)分离数等于 H 中两两内部点不交的(x, y)路的最大条数，即 sH (x, y)= (, ) Hr xy 。结合(∗)式和(∗∗)式，知 sH (x, y)= (, ) Hr xy = s(x, y) −1。设 U 是 H 的一个最小(x, y)分离集，由于 H 与 G 只相差一条边 e = uv，易见 U {} ∪ u 和 U {} ∪ v 都是 G 的(x, y)分离集。（3）用 ( ), ( ) NxNy G G 表示 x 和 y 在 G 中邻点的集合，则 () () Nx Ny G G ∩ = φ 。事实上，假如 () () Nx Ny G G ∩ ≠ φ ，则∃u ∈ () () Nx Ny G G ∩ 。设 H Gu = − 。由 G 的最小性，H 中(x, y)分离数等于 H 中两两内部点不交的(x, y)路的最大条数。与上述（2）的证明类似可知，图 H 的(x, y)分离数 sH (x, y) = s(x, y) −1，故 H 中存在 s(x, y) −1 条两两内部点不交的(x, y)路。显然它们和路 xuy 一起形成 G 的 s(x, y)条两两内部点不交的(x, y)路。这与 G 的取法矛盾。（4）记 k = s(x, y)。如果 1 2 {, , , } W ww w = " k 是 G 的一个最小(x, y)分离集，则 ( ) W Nx ⊆ G 或者 ( ) W Ny ⊆ G 。事实上，设 Gx、Gy为图G −W 中分别包含 x 和 y 的连通分支，用G1表示由 (G ) V W x ∪ 在 G 中导出的子图，G2 表示由 (G ) V W y ∪ 在 G 中导出的子图。显然 1 2 VV W (G ) (G ) ∩ = 。如果 1 υ(G ) 1 = + k ，则 (G ) { } V x x = ，此时结论显然成立。同理， 2 υ(G ) 1 = + k 时结论成立。下面假设 1 υ(G ) 2 ≥ + k ，且 2 υ(G ) 2 ≥ + k 。给G1添加一个新顶点 v*，将它与G1中属于 W 的每个顶点都连新边，这样获得的图记为G1 ∗ 。若G1 ∗ 中存在(x, v* )分离集 S 满足 | S | 1，故 U ≠ φ 。由结论（4），U {}1 ∪ v ( ) ⊆ N x G 或者 U {}1 ∪ v ( ) ⊆ N y G ，但由于 1 xv EG ∈ ( ) 及结论（３），可知 U () ⊆ N x G ，且 U ⊆ ( ) N y G ；同样，由结论（4），U {}2 ∪ v ( ) ⊆ N x G 或者 U {}2 ∪ v ( ) ⊆ N y G ，但上面已知 U () ⊆ N x G ，由结论（３）可知必定 U {}2 ∪ v ( ) ⊆ N x G ，从而 2 ( ) G v Nx ∈ 。这与 P 是 G 的最短(x, y)路矛盾。证毕。由 Menger 定理可得到 Whitney 定理的如下推广

中科院研究生院专业基础课：《图论与网络流理论》第二章 图的连通性（高随祥）

中科院研究生院专业基础课：《图论与网络流理论》第二章图的连通性（高随祥）