1
第二章 图的连通性
在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图 G
1
，删除一条边或一个顶点便可使其变得不连通；而对于图 G
2
，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图 G
3
，要破坏其连通性，则至少需要删除三条边或三个顶点。
本章主要讨论如何通过图的顶点集,边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画 1 连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的 2 连通和 k 连通性。
§ 2.1 割点和割边
定义 2.1.1 设 )(GVv∈,如果 )()( GwvGw >?,则称 v 为 G 的一个 割点 。
（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别） 。
例如，下图中 u,v 两点是其割点。
定理 2.1.1 如果点 v 是简单图 G 的一个割点，则边集 E(G)可划分为两个非空子集
1
E 和
2
E,
使得 ][
1
EG 和 ][
2
EG 恰好有一个公共顶点 v。
证明留作习题。
推论 2.1.1 对连通图 G，顶点 v 是 G 的割点当且仅当 vG? 不连通。
定理 2.1.2 设 v 是树 T 的顶点，则 v 是 T 的割点当且仅当 1)( >vd 。
证明：必要性：设 v 是 T 的割点，下面用反证法证明 1)( >vd 。
若 0)( =vd,则
1
KT?,显然 v 不是割点。
若 1)( =vd,则 vT? 是有 1)( vTν 条边的无圈图,故是树。 从而 )(1)( TwvTw ==? 。
因此 v 不是割点。
以上均与条件矛盾。
充分性：设 1)( >vd,则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条 ),( wu 路。因 T 是树，
uvw 是 T 中唯一的 ),( wu 路，从而 )(1)( TwvTw =>? 。故 v 是割点。证毕。
G
1
G
2
G
3
vu
2
推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。
证明：设 T 是 G 的生成树，则 T 至少有两个叶子 u,v，由上一定理知,u,v 都不是 T 的割点，
即 1)()( ==? TwuTw 。由于 uT? 是图 uG? 的生成树，故
)(1)()()( GwTwuTwuGw ===?=?,
因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。
定理 2.1.3 设 v 是连通图 G 的一个顶点，则下列命题等价,
（ 1） v 是 G 的割点；
（ 2） 存在 )(,GVwu ∈,使得 vwu ≠,且 v 在每条 ),( wu 路上；
（ 3） 存在 }{\)( vGV 的一个划分,}{\)( vGV WU ∪=,φ=WU ∩,使得对 Uu∈?
和 Ww∈?,v 在每条 ),( wu 路上。
证明,（ 1）?（ 3）因 v 是割点，故 vG? 至少有两个连通分支
1
G,
2
G 。令 )(
1
GVU = 而
}){)((\)(
1
vGVGVW ∪=,则对 Uu∈? 和 Ww∈?,u,w 分别属于 vG? 的不同的连通分支。可见 G 中所有的 ),( wu 路必经过 v（否则 vG?
中仍有
),( wu 路，这与 u,w 分别属于 vG? 的不同的连通分支矛盾） 。
（ 3）?（ 2）显然。
（ 2）?（ 1）若 v 在每条 ),( wu 路上，则 vG? 中不存在 ),( wu 路，即 vG? 不连通，故
v 是 G 的割点。
证毕。
定义 2.1.2 设 )(GEe∈,如果 )()( GweGw >?,则称 e 为 G 的一条 割边 。
例如下图中，边 uv，边 wu 都是其割边。
定理 2.1.4 边 e 是 G 的割边当且仅当 e 不在 G 的任何圈中。
证明：证其逆否命题,e 不是割边当且仅当 e 含在 G 的某个圈中。
必要性：设 e = xy 不是割边。假定 e 位于 G 的某个连通分支
1
G 中，则 eG?
1
仍连通。故在
eG?
1
中有 ),( yx 路 P,P + e 便构成
1
G 中一个含有 e 的圈。
充分性：设 e 含在 G 的某个圈 C 中，而 C 含于某连通分支
1
G 中，则 eG?
1
仍连通。故
)()( GweGw =?,这说明 e 不是割边。证毕。
定理 2.1.5 一个连通图是树当且仅当它的每条边都是割边。
证明：连通图 G 是树?G 无圈?任何边 e 不含在圈中?任何边 e 是 G 的割边。证毕。
vu
w
3
定理 2.1.6 设 e 是连通图 G 的一条边，则下列命题等价,
（ 1） e 是 G 的割边；
（ 2） e 不在 G 的任何圈上；
（ 3） 存在 )(,GVvu ∈,使得 e 在每条 ),( vu 路上；
（ 4） 存在 )(GV 的一个划分,)(GV WU ∪=,φ=WU ∩,使得对 Uu∈? 和 Ww∈?,
e 在每条 ),( wu 路上。
证明,（ 1）?（ 2）定理 2.1.4 已证。 （ 1）?（ 4）?（ 3）?（ 1）的证明与定理 2.1.3 的证明类似。
§ 2.2 连通度和边连通度
定义 2.2.1 对图 G，若 V(G)的子集 V′使得 )()( GwVGw >′?,则称 V′为图 G 的一个 顶点割集 。含有 k 个顶点的顶点割集称为 k－ 顶点割集 。
注,（ 1）割点是 1－顶点割集。
（ 2）完全图没有顶点割集。
定义 2.2.2 图 G 的 连通度 定义为 () min{| |GVVκ ′ ′= 是连通图 G 的顶点割集 }。特别地，
完全图的连通度定义为 1)(?=νκ
ν
K,空图的连通度定义为 0,不连通图的连通度定义为 0。
注,(1) 若 G 是平凡图，则 0)( =Gκ 。
(2) 使得 )(|| GV κ=′ 的顶点割集 V′称为 G 的 最小顶点割集 。
(3) 若 kG ≥)(κ,则称 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′使得 )()( GwEGw >′?,则称 E′为图 G 的一个 边割集 。含有 k 条边的边割集称为 k－边割集 。
注,(1) 对非平凡图 G，若 E′是一个边割集，则 EG ′\ 不连通。
(2) 一条割边构成一个 1－边割集。
(3) 设 )(GVS?,)(GVS?′,φ≠′SS,,记号 ],[ SS ′ 表示一端在 S 中另一端在 S′中的所有边的集合。对图 G 的每个边割集 E′，必存在非空的 )(GVS?,使得 ],[ SS 是 G 的一个边割集，其中 SVS \= 。
定义 2.2.4 图 G 的 边连通度 定义为 () min{| |GEEκ′ ′′= 是连通图 G 的边割集 }。完全图的边连通度定义为 1)(?=′ νκ
ν
K,空图的边连通度定义为 0，不连通图的边连通度定义为 0。
注,(1) 对平凡图 G,0)( =′ Gκ 。
(2) 是含有割边的连通图，则 1)( =′ Gκ 。
4
(3) 使得 )(|| GE κ′=′ 的边割集 E′称为 G 的 最小边割集 。
(4) 若 kG ≥′ )(κ,则称 G 为 k 边连通的 。
(5) 按上述定义，图 G 是 k 边连通的，当且仅当 G 的最小边割集至少含 k 条边，当且仅当 G 中没有 k?1 边割集，当且仅当从 G 中任意去掉 k?1 条边后，所剩图仍连通。
(6) 按照 k 边连通的定义,若图 G 是 k 边连通的,则它也是 k?1 边连通,k?2 边连通,…、
1 边连通的。因此，所有非平凡连通图都是 1 边连通的。
例如，下列图中,G
1
是连通的且有割点和割边，因此是 1 连通的和 1 边连通的； G
2
的最小点割集含 1 个点，最小边割集含 2 条边，故它是 1 连通的和 2 边连通的； G
3
的最小点割集和最小边割集分别含 2 个点和 2 条边，因此是 2 连通的和 2 边连通的； G
4
的最小点割集和最小边割集分别含 3 个点和 3 条边，因此是 3 连通的和 3 边连通的。
定理 2.2.1 )()()( GGG δκκ ≤′≤ 。
证明：先证 )()( GG κκ ′≤ 。
对图的边连通度 ()Gκ′ 作数学归纳法。
对 ()Gκ′ ＝ 1 的图 G，若
2
GK=,则显然 () 11Gκ υ′ =?=；若
2
GK≠,则 G 至少含三个点。设 e = uv 是 G 的一条割边，则 u 或 v 必是割点，故 ()Gκ =1。
总之，此时 ()Gκ = ()Gκ′ ＝ 1。
假设对所有 kκ′= 的图,都有 κκ′≤,则对 () 1Gkκ′ = + 的图 G,设 E是它的一个 1k +
边割集。任取边 ()euvEG=∈,则 Ee? 是 Ge? 的最小边割集，故 ()Ge kκ′?=。由归纳假设,()()Ge Geκκ′?≤?。取 Ge? 的最小点割集 T，则
||()()TGe Gekκκ′=?≤?=,
且 {}Tu∪ 构成 G 的最小点割集。 故 ()| {}|| |1 1 ()GTuT k Gκ κ′= ≤+≤+=∪ 。 归纳完成。
再证 )()( GG δκ ≤′ 。
设 δ=)(vd 。删去与 v 关联的 δ 条边后,G 变成不连通图，故这 δ 条边构成 G 的一个边割集。因此 )()( GG δκ ≤′ 。证毕。
下图 G
1
是一个 2,3κ κ′==和 4δ = 的图,G
2
是一个 1,2κ κ′= = 和 3δ = 的图。
G
1
G
2
G
3
G
4
G
1
G
2
5
定理 2.2.2 对具有 υ个顶点 ε 条边的连通图 G，有
2
()G
ε
κ
ν
≤
。
证明：因
()
2()
vVG
dvε δυ
∈
=≥
∑
，故
2ε
δ
υ
≤,由定理 2.2.1，
2ε
κδ
υ
≤≤ 。由于 κ 是整数，
因此
2ε
κ
ν
≤
。证毕。
定理 2.2.3 设 G 是一个简单图,k 是一个自然数，若
2
()
2
k
G
υ
δ
+?
≥,则 G 是 k 连通的。
证明：用反证法。假如 G 不是 k 连通的，则 G 的连通度 kκ <,即存在 G 的点割集 S，使得 ||Sk<,且 G?S 不连通。因 G?S 有 |S|υ? 个顶点，且至少有两个连通分支，故必有 G?S
的某个连通分支 G′含有不超过
|S|
2
υ?
个顶点。 注意到 G′中任一个顶点只可能与 G′内的点及 S 中的点相邻，因而其在 G 中的顶点度
|| |S|2
1| |
22
S
S
υ υ? +?
≤?+= 。结合 ||Sk<,
这意味着 (G)δ ≤
||2 2
22
Skυ υ+?+?
<,与定理条件矛盾。证毕。
推论 2.2.1 设 G 是一个简单图，若
1
()
2
G
υ
δ
≥,则 G 是连通的。
定理 2.2.4 设 G 是一个直径为 2 的简单图，则 (G) (G)κ δ′ = 。
证明：设 S 是 G 的一个最小边割集，则 G?S 有多于一个连通分支，取其中顶点数最少的一个记为 G
1
,G?S 的其余部分记为 G
2
。
如果 G
1
中存在顶点 u，它在 G 中不与 G
2
的顶点相邻，则对，由 (,) 2
G
duv= 知，在 G
中 v 有属于 G
1
的邻点。由此可知，在 G 中来看，要么 G
1
中每个点都在 G
2
中有邻点，要么
G
2
中每个点都在 G
1
中有邻点。在前一种情况下，
1
|S| (G )υ≥,在后一种情况下，
2
|S| (G )υ≥ 。总之，
12 1
|S| min{ (G ),(G )} (G )κυυυ′=≥ = 。 （ 1）
对
1
uG?∈,用
1
()du和
1
()du分别表示在 G 中 u 与 G
1
和 G
2
连的边数。则
12 1 2
( ) () () () ( ) 1 ()
G
Gdududu G duδ υ≤=+≤?+。
根据定理 2.2.1,
(G)κδ′≤≤
12
()1 ()Gduυ? + 。 （ 2）
结合（ 1）式可得
2
() 1du≥ 。 任取
01
()uVG∈,由于
110
2220120
| | () () ( ) ( ) 1 ( )
uG uG u
Sdu duduG duκυ
∈∈?
′== = + ≥?+
∑∑
,
结合（ 2）式得
6
120
()1 ()Gduυ?+ ≤ (G)κ δ′≤ ≤
120
()1 ()Gduυ? +
可见 (G)κδ′= 。证毕。
推论 2.2.2 设非空简单图 G 中任二不相邻顶点 u 和 v 都满足 () () 1du dv υ+ ≥?，则
(G) (G)κδ′ = 。
证明：若 G 中任意两点都相邻，则 G 是完全图,(G) 1 (G)κ υδ′ =?=,结论成立。若 G
中有不相邻顶点,则 diam 2G ≥ 。 但由于任二不相邻顶点 u和 v都满足 () () 1du dv υ+≥?，
即任二不相邻顶点 u 和 v 都有公共的邻点。因此又有 diam 2G ≤ 。从而 diam 2G = 。由定理 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－连通图。 （若只有两个顶点，则有反例，例如
2
K 是个块，但不是 2 连通的。 ）
关于 2 连通图（块）,有下列重要结论。
定理 2.3.1 (Whitney,1932) 3≥ν 的图 G 是 2－连通图（块）当且仅当 G 中任二顶点共圈。
证明：充分性：设 G 中任二顶点在同一圈上，欲证 G 是 2－连通的。
对 )(GVw∈?,任取 )(,wGVvu?∈ 。由条件,u,v 在 G 中共处于某个圈 C 上。若
Cw?,则在 wG \ 中 u,v 仍在圈 C 上；若 Cw∈,则 wG? 中 u,v 在路 wC? 上。总之
u,v 在 wG? 中有路相连。由 u,v 的任意性,wG? 是连通图，故 w 不是 G 的割点。再由 w
的任意性知,G 无割点，即 G 是 2－连通的。
7
必要性：设 G 是 2－连通图，欲证任二顶点 u,v 都在同一圈上。
对距离 ),( vud 作归纳法。
1),( =vud 时，因 2≥≥′ κκ,故 G 中无割边,uvG? 仍连通。因此 uvG? 中存在一条 ),( vu 路
1
P 。这表明在 G 中 u,v 都在圈 uvP +
1
上。
假定 kvud <),( 时，结论成立。下证 kvud =),( 时结论也成立。
当 kvud =),( 时，设 wvuP null=
0
是长为 k 的一条 ),( vu 路，则 1),(?= kwud 。由归纳法假设,u,w 在同一圈上，故在 u,w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连通图，故 wG? 仍连通。在 wG? 中存在 ),( vu 路 P′。令 x 是 P′上最后一个与 QP ∪ 的公共顶点（因 QPu ∪∈,这样的 x 存在） 。不妨设 Px∈,则 P 上 ),( xu 段＋ P′上 ),( vx 段与 wvQ + 是两条内部无公共点的 ),( vu 路。故 u,v 在同一圈上。归纳法完成。证毕。
推论 2.3.1 3≥ν 的图 G 是 2 连通图（块）当且仅当 G 中任二顶点被至少两条内部无公共顶点的路所连。
推论 2.3.2 若 3≥ν 的图 G 是 2 连通图（块）,则 G 的任二边都位于同一圈上。
证明：设 G 是 3≥ν 的 2 连通图，且 )(,
21
GEee ∈,在
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） 对 )(,GVvu ∈? 及 )(GEe∈?,存在 ),( vu 路含有边 e；
（ 6） 对 )(,,GVwvu ∈?,存在 ),( vu 路含有顶点 w;
（ 7） 对 )(,,GVwvu ∈?,存在 ),( vu 路不含有顶点 w。
证明,（ 1）?（ 2）见 Whitney 定理。
（ 2）?（ 3）设 G 中任二顶点共圈。对 )(GVu∈? 及 )(GExye ∈=?,若 ux = 或 uy =,
则结论显然。以下假定 uyx ≠,。设 C 是含 u 与 x 的圈。若 Cy∈,则 C 上含有 u 的 ),( yx
P
P
0
u
P′
v
Q
x
w
8
路与边 x y 形成一个圈，它含有 u 及边 e；
设 Cy? 。由 Whitney 定理,x 不是割点。故存在不含 x 的 ),( yu 路 P，令 w 是 P 上从 y
出发第一个与 C 公共的顶点，则 C 上 x-u-w 段＋ P 上 ),( yw 段＋ xy 构成一个含 u 和 e = xy
的圈。
（ 3）?（ 4）,与（ 2）?（ 3）类似可证。
（ 4）?（ 5）,设 G 中任二边共圈。对 )(,GVvu ∈? 及 )(GEe∈?,如果 uve =,结论显然成立；如果 u 或 v 之一是 e 的端点，比如 u 是 e 的端点而 v 的一个邻点是 w，则 e 与边
wv 共圈，故显然有 ),( vu 路含有边 e。
下面假定 u 和 v 都不是 e 的端点。
因任二边共圈显然任二点共圈，故由（ 2）?（ 3）知 u 与 e 共圈,v 也与 e 共圈。设这二圈分别是
1
C 和
2
C 。若
2
Cu∈ 或
1
Cv∈,则结论成立；若
2
Cu? 且
1
Cv?,则如下构作含 e 的 ),( vu 路：从 u 出发沿
1
C 到达
1
C 与
2
C 的第一个公共顶点 w，再从 w 出发沿
2
C 含 e
的部分到达 v，即可。
（ 5）?（ 6）,对 )(,,GVwvu ∈?,设与 w 相关联的一条边为 e。由（ 5）,存在 ),( vu 路含有边 e，于是含有 w。
x
u
y
u
vw
e
w
C
1
e
v
u
C
2
w
x
u
y
9
（ 6）?（ 7）,对 )(,,GVwvu ∈?,存在 ),( wu 路 P 含有顶点 v，则 P 的从 u 到 v 的一段不含有 w。
（ 7）?（ 1）,因为对 )(GVw∈? 及 )(,GVvu ∈?,存在 ),( vu 路不含有顶点 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)υ υ<,要么 (G) (H)υ υ= 且 (G) (H)ε ε≤ 。
下面证明该图 G 的四条结论。
（ 1）按照上述取法，由于 s(x,y) > 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| (,) 1sxy=?
且 U{}u∪ 和 U{}v∪ 都是 G 的 (x,y)分离集。
事实上，设 e = uv,H = G? e。 H 的 (x,y)分离数
s
H
(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)路的条数
(,)
H
rxy≤ r (x,y)≤ s(x,y)?1。 ()
10
由 G 的最小性可知,H 中的 (x,y)分离数等于 H 中两两内部点不交的 (x,y)路的最大条数，即
s
H
(x,y)= (,)
H
rxy。结合 (?)式和 ()式，知 s
H
(x,y)= (,)
H
rxy= s(x,y)?1。设 U 是 H 的一个最小 (x,y)分离集,由于 H 与 G 只相差一条边 e = uv,易见 U{}u∪ 和 U{}v∪ 都是 G 的 (x,
y)分离集。
（ 3）用 (),()
GG
NxNy表示 x 和 y 在 G 中邻点的集合，则 () ()
GG
Nx Ny φ=∩ 。
事实上，假如 () ()
GG
Nx Ny φ≠∩,则 u? ∈ () ()
GG
Nx Ny∩ 。设 HGu=?。由 G
的最小性,H 中 (x,y)分离数等于 H 中两两内部点不交的 (x,y)路的最大条数。与上述（ 2）的证明类似可知，图 H 的 (x,y)分离数 s
H
(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)。如果
12
{,,,}
k
Www w= null 是 G 的一个最小 (x,y)分离集，则
()
G
WNx? 或者 ()
G
WNy? 。
事实上,设 G
x
,G
y
为图 G W? 中分别包含 x 和 y 的连通分支,用
1
G 表示由 (G )
x
VW∪
在 G 中导出的子图，
2
G 表示由 (G )
y
VW∪ 在 G 中导出的子图。 显然
12
(G ) (G )VV W=∩ 。
如果
1
(G ) 1kυ =+，则 (G ) { }
x
Vx=,此时结论显然成立。同理，
2
(G ) 1kυ =+时结论成立。下面假设
1
(G ) 2kυ ≥+，且
2
(G ) 2kυ ≥+。给
1
G 添加一个新顶点 v*，将它与
1
G 中属于 W 的每个顶点都连新边，这样获得的图记为
1
G
。若
1
G
中存在 (x,v* )分离集 S 满足 | S
| < k，则易见 S 也是 G 的 (x,y)分离集，这与 G 的最小 (x,y)分离集 W 含 k 个点矛盾。由此可知，
1
G
的 (x,v* )分离数为 k。因
1
G
的阶小于 G 的阶，由 G 的最小性，
1
G
中任二点的分离数等于
1
G
中该两点间两两内部点不交路的最大条数。 因此
1
G
中有 k 条两两内部点不交的 (x,
v* )路。由
1
G
的结构可知，这 k 条路从 x 出发分别连到 W 的不同顶点。同理可知，从 y 出发也有 k 条两两不交的路分别连到 W 的不同顶点。这些路连接成 G 中 k 条两两内部点不交的 (x,y)路。这与 G 的取法矛盾。
现在继续完成定理的证明。
设 P 是 G 中一条最短的 (x,y)路。由结论（ 3）,P 的长至少为 3。设
12 t
Pxvv vy= null 。
按照结论（ 2）,存 在 G 的顶点子集 U，满足 |U| (,) 1sxy=? 且
1
U{}v∪ 和
2
U{}v∪ 都是 G
的 (x,y)最小分离集。由结论（ 1）,s(x,y) > 1，故 U φ≠ 。由结论（ 4）,
1
U{}v∪ ()
G
Nx?
或者
1
U{}v∪ ()
G
Ny?,但由于
1
()xvEG∈ 及结论（ ３ ）,可知 U()
G
Nx?,且
U? ()
G
Ny；同样，由结论（ 4）,
2
U{}v∪ ()
G
Nx? 或者
2
U{}v∪ ()
G
Ny?,但上面已知 U()
G
Nx?,由结论（ ３ ）可知必定
2
U{}v∪ ()
G
Nx?,从而
2
()
G
vNx∈ 。这与 P 是
G 的最短 (x,y)路矛盾。证毕。
由 Menger 定理可得到 Whitney 定理的如下推广
11
推论 2.4.1 1+≥ kν 的图 G 是 k 连通图当且仅当 G 中任二顶点至少被 k 条两两内部无公共顶点的路所连。
证明：必要性：用反证法。设 G 是 k 连通图。假定 G 中存在两个顶点 x,y，它们之间两两内部无公共顶点的路最多只有 m 条,m < k。分两种情况考虑。
(1) 如果 (G)xy E?,则因 G 中最小点割集的点数不超过 G 中最小 (x,y)分离集的点数，
由 Menger 定理,() (,)Gsxymkκ ≤=<。这与 G 是 k 连通图矛盾。
（ 2）如果 (G)xy E∈,则 H= G xy? 中两两内部无公共顶点的 (x,y)路最多只有
11mk?<?条。 由 Menger 定理,()(,)11
H
Gxy sxy m kκ? ≤=?<?。因此，存在
G xy? 的一个顶点子集 U,使得 |U| 2k≤?,且 (G ) Uxy 不连通。 故图 G(U{})x? ∪
和 G(U{})y? ∪ 中，至少有一个是不连通图，这表明 G 有不超过 k?1 个点的点割集，与 G
是 k 连通图矛盾。
充分性：用反证法。设 G 中任二顶点至少被 k 条两两内部无公共顶点的路所连。假如 G 不是 k 连通图，则 (G) kκ < 。设 W 是 G 的一个最小点割集，则 |W| (G) kκ= < 。从 GW?
的两个不同连通分支中各取一个点 x 和 y。由充分性的前提条件,x 和 y 在 G 中至少被 k 条两两内部无公共顶点的路所连，即 (,)rxy k≥ 。由 Menger 定理,G 中 (x,y)分离数 s(x,y)
= (,)rxy k≥,但因 |W| k<,故 x,y 在 GW? 中仍连通，这与 x,y 的取法矛盾。
证毕。
关于边连通有与 Menger 定理类似的结果，称为边形式的 Menger 定理。它的证明与
Menger 定理类似。
设 G 是一个简单图,x,y 是 G 中任二不同顶点。 如果从 G 中删去一组边后不再有 (x,y)
路则称这组边 分离 x 和 y，而称这组边为一个 (x,y)边分离集。 G 中含边数最少的 (x,y)边分离集称为 最小 (x,y)边分离集,其边数称为 G 的 (x,y)边分离数,记为 (,)sxy′ 。此外，将 G 中两两边不交的 (x,y)路的最大条数记为 (,)rxy′ 。
定理 2.4.2（边形式 Menger 定理）对任意图 G，设 x,y 是 G 中两个不相邻顶点，则 G 中分离 x,y 所需的最少边数等于 G 中两两边不交的 (x,y)路的最大条数，即 (,)sxy′ = (,)rxy′ 。
利用边形式 Menger 定理能够给出一个与推论 2.4.1 类似的边形式的结果，其证明与与推论 2.4.1 类似。
推论 2.4.2 图 G 是 k 边连通图当且仅当 G 中任二顶点至少被 k 条两两无公共边的路所连。
求图中点不交路和边不交路的算法可参看文献
N,Robertson,and P.D,Seymour,Outline of a disjoint paths algorithm,in Paths,Flows and
VLSI-Layout (B,Korte,L.Lovasz,H.J,Promel,and A,Schrijver editors),Springer-Verlag,Berlin,
1990,
J.M,Kleinberg,Approximation algorithms for disjoint paths problems,Ph.D thesis,MIT,
Cambridge,MA,May 1996,
12
A,Srinivasan,Improved approximations for edge-disjoint paths,unsplittable flow and related
routing problems,in Proc,38
th
Ann,Symp.on Foundations of Computer Science,1997,416-425,
S,G,Kolliopoulos,and C,Stein,Approximating disjoint-path problems using greedy algorithms
and packing integer programs,in Proceedings of 6
th
International IPCO Conference,Houston,
Texas,1998,
§ 2.5 可靠通信网络的设计
可靠网络设计问题,给定赋权图 G 和正整数 m，求 G 的具有最小权的 m 连通生成子图。
当 1=m 时，就是求最小生成树问题。
当 1>m 时，问题尚未解决。
当
n
KG = 且每边权皆为 1 时，问题成为：求
n
K 中边数最少的 m-连通生成子图。这一问题于 1962 年由 Harary 所解决。
令 ),( nmf 表示有 n 个顶点的 m 连通图所能具有的最少边数（ nm < ） 。设 G 是一个具有这种性质且有 ),( nmf 条边的图。因
∑
∈
=
)(
)(2
GVv
vdε,而 δκκ ≤′≤ 。故
),( nmf
22
)(
2
1
)(
mnn
vd
GVv
≥≥=
∑
∈
δ
。
Harary 找到了具有 n 个顶点、
2
mn
条边的 m 连通图。这种图记为
nm
H
,
，构造如下：
记
nm
H
,
的顶点集为 }1,,2,1,0{?nnull 。
（ 1） 若 m 为偶数，设 rm 2= 。当且仅当 )(mod20 nrrij ≤+?≤ 时，顶点 i 与 j 连边；
（ 2） 若 m 为奇数（设 12 += rm ）,而 n 是偶数，则先构作
2,rn
H,然后对
2
1
n
i ≤≤ 的
i，在顶点 i 与
2
n
i + 间加上一条边；
（ 3） 若 m 为奇数 （设 12 += rm ）,且 n 也是奇数,则先构作
nr
H
,2
,然后对
2
1
1
<≤
n
i
的 i，在顶点 i 与
2
1+
+
n
i 间加上一条边，再在顶点 0 与
2
1?n
,0 与
2
1+n
之间各加上一边。
H
4,8
(m=4,r=2,n=8) H
5,8
(m=5,r=2,n=8) H
5,9
(m=5,r=2,n=9)
3
2
1
0
5
4
7
6
5
2
1
0
4
3
7
6
8
3
2
1
0
5
4
7
6
13
定理 2.5.1
nm
H
,
是 m 连通的。
证明：只证 rm 2= 的情况。 12 += rm 的情况类似可证。
我们用反证法来证明
nm
H
,
中没有少于 rm 2= 个顶点的点割集。
若不然，设 V′是一个点割集且 rV 2|| <′ 。又设 i 与 j 是 VH
nr
′?
,2
中属于不同连通分支的两个顶点。考察顶点集
},1,,1,{ jjiiS?+= null 和 },1,,1,{ iijjT?+= null 。
这里加法取模 n。因 rV 2|| <′ 且 Vji ′?,，不失一般性，设 rVS <′|| ∩ 。则在 VS ′\ 中必存在一个始于 i 而终于 j，且任二相继项之差 r≤ 的序列。但由
nr
H
,2
的构成（ 1）,这样的序列中相邻项之间存在边。因此这个序列构成了 VH
nr
′\
,2
中一条 ),( ji 路。这与 i,j 的取法矛盾。证毕。
推论 2.5.1 ),( nmf ＝
2
mn
。
证明：容易检查 )(
,nm
Hε ＝
2
mn
。由上一定理，
nm
H
,
是 m 连通的，故
≤),( nmf =)(
,nm
Hε
2
mn
。
另一方面，前已述及 ≥),( nmf
2
mn
。故 ),( nmf ＝
2
mn
。证毕。
注,因 κκ ′≤,故
nm
H
,
也是 m 边连通的。若 ),( nmg 表示 n 个顶点的 m 边连通图可能的最少边数，则 ),( nmg ＝
2
mn
。
关于图的连通性和边连通性的更多内容可参看文献,
[1] J.A,Bondy,and U.S.R,Murty,Graph Theory with Applications,The Macmillan Press LTD,
1976.（中译本：吴望名、李念祖、吴兰芳、谢伟如、梁文沛译，图论及其应用，科学出版社,1984） 。
[2] D.B,West,Introduction to Graph Theory (second edition),Prentice-Hall,Inc.,(2001)149-190,
（中译本：李建中、骆吉周译，图论导引，机械工业出版社,2006） 。
[3]W.T,Tutte,Graph Theory,Cambridge University Press,(2001) 32-114.(影印版：图论，机械工业出版社,2004),
[4] D,Reinhard,Graph Theory (second edition),Springer-Verlag,New York,(2000)43-67,(影印版：图论，世界图书出版公司,2003),
[5] W,Mader,Connectivity and edge-connectivity in finite graphs,London Math,Lecture Note
Series,38(1979)66-95,
[6] J.C,Bermond,N,Homobono and C,Peyrat,Large fault-tolerant interconnection networks,
Graphs and Combinatorics,Springer,5(1989),107-123,
[7] D.F,Hsu,On container width and length in graphs,groups and networks,IEICE Trans,
14
Fundam,1994,E(77A),668-680,
[8] D.W,Matula,Determine edge connectivity in O(mn),Proc,28
th
Symp,On Foundations of
Computer Science,1987,249-251,
[9] J,Cheriyan,S,Vempala and A,Vatta,Approximation algorithms for minimum-cost k-vertex
connected subgraphs,Proceeding of the 34
th
Annual ACM Symposium on Theory of Computing,
Canada,2002,pp306-312,
[10] N,Lichiardopol,Broadcast time and connectivity,Discrete Applied Mathematics,143(2004),
359-363,
[11] T,Jordán,On minimally k-edge-connected graphs and shortest k-edge-connected Steiner
networks,Discrete Applied Mathematics,131(2003),421-432,
[12] P,Dankelmann and O,R,Oellermann,Bounds on the average connectivity of a graph,
Discrete Applied Mathematics,129 (2003),305-318,
[13] E,Oh and J,Chen,On strong Menger-connectivity of star graphs,Discrete Applied
Mathematics,129 (2003),499-511,
[14] J.Bang-Jensen,H,N,Gabow,T,Jordán,and Z,Szigeti,Edge-Connectivity Augmentation
with Partition Constraints,SIAM J,on Discrete Mathematics,12(1999),160-207,
[15] J,Cheriyan,A,Sebo,and Z,Szigeti,Improving on the 1.5-Approximation of a Smallest
2-Edge Connected Spanning Subgraph,SIAM J,on Discrete Mathematics,14(2001),170-180,
[16] T,Erlebach and K,Jansen,The Maximum edge-disjoint paths problem in bidirected trees,
SIAM J,on Discrete Mathematics,14(2001),326-355,
[17] D,Huygens,A,R,Mahjoub,and P,Pesneau,Two Edge-Disjoint Hop-Constrained Paths and
Polyhedra,SIAM J,on Discrete Mathematics,18(2004-2005),287-312
[18] H,N,Gabow,An Improved Analysis for Approximating the Smallest k-Edge Connected
Spanning Subgraph of a Multigraph,SIAM J,on Discrete Mathematics,19(2005),pp,1-18,
[19]G,Kortsarz,R,Krauthgamer,and J,R,Lee,Hardness of Approximation for
Vertex-Connectivity Network Design Problems,SIAM J,on Computing,33(2003-2004),704-720
[20] M,Katz,N,A,Katz,A,Korman,and D,Peleg,Labeling Schemes for Flow and Connectivity,
SIAM J,on Computing,34(2004-2005),23-40,
[21] 张先迪，李正良，图论及其应用，高等教育出版社,2005。
[22] 蒋长浩，图论与网络流，中国林业出版社,2001。
第二章习题
1,证明,若 G 是连通简单图但不是完全图,则 G 中必存在三个顶点 u,v 和 w,使得,uv vw E∈
而 uw E? 。
2,证明恰有两个顶点不是割点的简单连通图是一条路。
3,证明：点 v 是图 G 的割点当且仅当 v 至少属于 G 的两个不同的块。
4,证明或否定：如果直径为 2 的简单图有一个割点，则其补图有一个孤立顶点。
5,若一个图 G 至少有一条非环边，则 G 至少有两个非割点。
15
6,若 v 是简单图 G 的一个割点，则 Gv? 是连通的。
7,设 G 是自补图，证明,G 有割点当且仅当 G 有 1 度点。
8,证明：恰有两个顶点不是割点的简单连通图是一条路。
9,举反例说明下面的命题不成立,然后添加一个假设条件使其成立并证明所得命题的正确性：如果 e 是图 G 的一条割边，则 e 至少有一个端点是 G 的割点。
10,证明：若 G 的每个顶点均为偶度顶点，则 G 无割边。
11,证明顶点度全为偶数的图没有割边。对任意 1k ≥,构造具有一条割边的 21k + 正则简单图。
12,对于 2k ≥,证明：一个 k 正则二部图没有割边。
13,设 G 连通且 ()eEG∈ 。证明,e 在 G 的每棵生成树中当且仅当 e 是 G 的割边。
14,设 G 是一个图。
(1) 证明 G 是一棵树当且仅当它中连通的且其每条边都是割边；
(2) 证明 G 是一棵树当且仅当添加任一条以 ()VG中顶点为端点的边构成唯一一个圈。
15,证明：连通图 G 的一条边 e 是割边当仅且当 e 属于任何一棵生成树； e 是一个圈当且仅当 e 不属于任何一棵生成树。
16,令 C 是加权图中的一个圈，设 e 是 C 上权值最大的非割边，证明：存在一棵不包含 e
的最小生成树。由此证明：不断删除图中权值最大的非割边，直到剩下的图没有圈为止，最后将得到一棵最小生成树。
17,设 G 是一个直径为 2 的图,S 是 G 的一个最小边割集。证明,G－ S 的连通分支至少有一个同构于 K
1
或
(G)
K
δ
。
18,设 A,B 是两个集合，集合 (A B) (B A)∪ 称为 A 与 B 的对称差，记为 AB⊕ 。
证明,(1) AB⊕ = (A B) (A B)?∪∩； (2) 图 G 的两个边割集的对称差仍是 G 的边割集。
19,证明或否定：如果一个简单图 G 的最大度是
2
υ
，最小度是 1
2
υ
，则 G 是连通的。
20,证明：若 G 是简单图且其最小度 2δ≥ν?,则连通度 ()Gκ =δ。
21,对下面的每个图 G，确定其连通度、边连通度和最小顶点度。
22,构造一个连通度为 1 的 3 正则简单图。
23,证明：对图 G 的任一条边 e,(G ) (G) 1eκκ? ≥?。
24,证明：如果 G 是 3 正则简单图，则 (G) (G)κ κ′= 。
16
25,证明：若 G 是简单图且 (G) 3Δ≤，则 (G) (G)κ κ′= 。
26,设 H 是连通图 G 的子图。举例说明：有可能 (H) (G)κ κ> 。
27,设 G 是度至少为 2 的正则二部图，证明,(G) 1κ ≠ 。
28,一个单圈图是指仅含有一个圈的图。 (1) 证明：如果 G 是单圈图，则 (G) 2κ ≤ 且
(G) 2κ′ ≤ ； (2) 对所有单圈图 G 均有 (G) (G) 2κ κ′= = 吗？
29,证明或举反例,(1) 任何 k 连通图都是 k 边连通图； (2) 任何 k 边连通图都是 k 连通图。
30,证明：若 G 是 k 边连通的，则
2
k
ν
ε≥?。
31,证明：图 G 是 k 连通的当且仅当
n
GK∨ 是 k + n 连通的。这里
n
GK∨ 表示将 G 的每个顶点与完全图
n
K 的所有顶点都连边构成的图。
32,设 G 是连通图，且对其每条边 e，都存在两个包含 e 的圈 C
1
和 C
2
使得二者的唯一公共边为 e。证明 G 是 3 边连通的。由此证明 Peterson 图是 3 边连通的。
33,证明：连通图 G 是 k 边连通的当且仅当它的每个块都是 k 边连通的。
34,证明：图的每个顶点的度都是偶数当且仅当 G 的每个块都是欧拉图。
35,证明：若简单图 G 无偶圈，则 G 的每个块要么是 K
2
要么是奇圈。
36,证明：对不是块的连通图，至少有两个块，它们每个恰含有 G 的一个割点。
37,对非平凡连通图 G，定义 G 的块－割点图 B(G)为,B(G)的顶点集由 G 的所有块和割点组成,B(G)中两个顶点连边当且仅当一个是 G 的割点而另一个是 G 的包含该割点的块。
证明 B(G)是一棵树。
38,证明：若简单图 G 是一个 (G) 3δ ≥ 的块，则 G 中必存在顶点 v，使得 G v? 也是块。
39,设 G 是连通图并且其所有的块为 B
1
,B
2
,…,B
k
,证明 G 恰有 (() 1
k
i
ii
Bkυ
=
+
∑
个顶点。
40,设 G 是至少含有 3 个顶点的连通图，在 G 中距离为 2 的顶点对间全部添加新边，所得之图记为 G′。证明 G′是 2 连通的。
41,设 G 是一个连通图。 试给出一个公式,用 G 的块的生成树数目表示 G 的生成树的数目。
42,设 G 是一个块,x 和 y 是 G 的不同顶点。如果 P 是 G 中一条 (x,y)路，问 G 中是否一定存在一条与 P 内部点不交的路？
43,证明：图 G 是 2－边连通的当且仅当 G 的任二顶点至少由两条边不重的路所连。
44,设 G 是一个 k 连通图，
12
,,,
k
vv vnull 是 G 中 k 个不同的顶点。给 G 添加一个新顶点 w，
并将 w到上述 k个顶点都连上边,这样对 G修改之后所得之图记为 G′。 证明 (G ) kκ ′ = 。
45,设 G 是 k 连通图，且 H＝ G + K
1
(由完全图 K
1
的顶点向 G 的所有顶点连边构成之图 )，
17
证明 H 是 k+1 连通的。
46,设 G 是一个 k 连通图且 v 是 G 的一个顶点。对任意正整数 m，定义 G
m
是由 G 添加 m
个新顶点
12
,,
m
ww wnull 和所有形如,(1,( ))
iG
wu i m u N v≤ ≤∈ 的边后所得之图。证明
G
m
是 k 连通的。
47,证明或否定：如果 G 是一个 k 边连通图且 v,
12
,,
k
vv vnull 是 G 的 k+1 个不同顶点，那么对每个 1,2,,ik= null,都存在（ v,v
i
）路 P
i
,P
i
恰好包含 {
12
,,
k
vv vnull }中一个顶点 v
i
，
且当 ij≠ 时,P
i
和 P
j
是边不交的。
48,设图 G 满足,(G) 3κ =,且存在不相邻的顶点 x 和 y 使得 G 的 (x,y)分离数为 4。问,
（ 1）在 G 中内部点不交的 (x,y)路的最大数是多少？
（ 2）给出一个满足上述性质的图的例子。
49,证明：对任何图 G，有
2
(G)
ε
κ
υ
≤
及
2
(G)
ε
κ
υ
′ ≤
。
50,设图 G 是 k 连通的，证明必有 (G) kδ ≥ 。
51,设图 G 是 k 连通的，证明对 G 中任何一个顶点 v,G v? 是 k?1 连通的。
52,（ 1）设图 G 是 k 边连通的，且 k > 0，证明,若 E′是 G 的 k 条边的集合，则连通分支数 (G E ) 2w ′?≤；
（ 2）对 k > 0，找出一个 k 连通图 G 及 G 的 k 个顶点的子集 V′，使得 (G V ) 2w ′?>。
53,证明：若 G 是 k 边连通的，则
2
kυ
ε ≥ 。
54,（ 1）证明：若 G 是简单图且 (G) 2δ υ≥?，则 (G) (G)κ δ= 。 （ 2）找出一个简单图，
使得 (G) 3δ υ=?且 (G) (G)κδ< 。
第二章 图的连通性
在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图，其连通的程度也有高有低。例如，下列三个图都是连通图。对于图 G
1
，删除一条边或一个顶点便可使其变得不连通；而对于图 G
2
，至少需要删除两条边才能使其不连通，也可以删除一个顶点使其不连通；对于图 G
3
，要破坏其连通性，则至少需要删除三条边或三个顶点。
本章主要讨论如何通过图的顶点集,边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画 1 连通图的特性；定义连通度和边连通度来度量连通图连通程度的高低；通过不交路结构和元素的共圈性质来反映图的 2 连通和 k 连通性。
§ 2.1 割点和割边
定义 2.1.1 设 )(GVv∈,如果 )()( GwvGw >?,则称 v 为 G 的一个 割点 。
（注：该定义与某些著作中的定义有所不同，主要是在环边的顶点是否算作割点上有区别） 。
例如，下图中 u,v 两点是其割点。
定理 2.1.1 如果点 v 是简单图 G 的一个割点，则边集 E(G)可划分为两个非空子集
1
E 和
2
E,
使得 ][
1
EG 和 ][
2
EG 恰好有一个公共顶点 v。
证明留作习题。
推论 2.1.1 对连通图 G，顶点 v 是 G 的割点当且仅当 vG? 不连通。
定理 2.1.2 设 v 是树 T 的顶点，则 v 是 T 的割点当且仅当 1)( >vd 。
证明：必要性：设 v 是 T 的割点，下面用反证法证明 1)( >vd 。
若 0)( =vd,则
1
KT?,显然 v 不是割点。
若 1)( =vd,则 vT? 是有 1)( vTν 条边的无圈图,故是树。 从而 )(1)( TwvTw ==? 。
因此 v 不是割点。
以上均与条件矛盾。
充分性：设 1)( >vd,则 v 至少有两个邻点 u,w。路 uvw 是 T 中一条 ),( wu 路。因 T 是树，
uvw 是 T 中唯一的 ),( wu 路，从而 )(1)( TwvTw =>? 。故 v 是割点。证毕。
G
1
G
2
G
3
vu
2
推论 2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。
证明：设 T 是 G 的生成树，则 T 至少有两个叶子 u,v，由上一定理知,u,v 都不是 T 的割点，
即 1)()( ==? TwuTw 。由于 uT? 是图 uG? 的生成树，故
)(1)()()( GwTwuTwuGw ===?=?,
因此 u 不是 G 的割点。同理 v 也不是 G 的割点。证毕。
定理 2.1.3 设 v 是连通图 G 的一个顶点，则下列命题等价,
（ 1） v 是 G 的割点；
（ 2） 存在 )(,GVwu ∈,使得 vwu ≠,且 v 在每条 ),( wu 路上；
（ 3） 存在 }{\)( vGV 的一个划分,}{\)( vGV WU ∪=,φ=WU ∩,使得对 Uu∈?
和 Ww∈?,v 在每条 ),( wu 路上。
证明,（ 1）?（ 3）因 v 是割点，故 vG? 至少有两个连通分支
1
G,
2
G 。令 )(
1
GVU = 而
}){)((\)(
1
vGVGVW ∪=,则对 Uu∈? 和 Ww∈?,u,w 分别属于 vG? 的不同的连通分支。可见 G 中所有的 ),( wu 路必经过 v（否则 vG?
中仍有
),( wu 路，这与 u,w 分别属于 vG? 的不同的连通分支矛盾） 。
（ 3）?（ 2）显然。
（ 2）?（ 1）若 v 在每条 ),( wu 路上，则 vG? 中不存在 ),( wu 路，即 vG? 不连通，故
v 是 G 的割点。
证毕。
定义 2.1.2 设 )(GEe∈,如果 )()( GweGw >?,则称 e 为 G 的一条 割边 。
例如下图中，边 uv，边 wu 都是其割边。
定理 2.1.4 边 e 是 G 的割边当且仅当 e 不在 G 的任何圈中。
证明：证其逆否命题,e 不是割边当且仅当 e 含在 G 的某个圈中。
必要性：设 e = xy 不是割边。假定 e 位于 G 的某个连通分支
1
G 中，则 eG?
1
仍连通。故在
eG?
1
中有 ),( yx 路 P,P + e 便构成
1
G 中一个含有 e 的圈。
充分性：设 e 含在 G 的某个圈 C 中，而 C 含于某连通分支
1
G 中，则 eG?
1
仍连通。故
)()( GweGw =?,这说明 e 不是割边。证毕。
定理 2.1.5 一个连通图是树当且仅当它的每条边都是割边。
证明：连通图 G 是树?G 无圈?任何边 e 不含在圈中?任何边 e 是 G 的割边。证毕。
vu
w
3
定理 2.1.6 设 e 是连通图 G 的一条边，则下列命题等价,
（ 1） e 是 G 的割边；
（ 2） e 不在 G 的任何圈上；
（ 3） 存在 )(,GVvu ∈,使得 e 在每条 ),( vu 路上；
（ 4） 存在 )(GV 的一个划分,)(GV WU ∪=,φ=WU ∩,使得对 Uu∈? 和 Ww∈?,
e 在每条 ),( wu 路上。
证明,（ 1）?（ 2）定理 2.1.4 已证。 （ 1）?（ 4）?（ 3）?（ 1）的证明与定理 2.1.3 的证明类似。
§ 2.2 连通度和边连通度
定义 2.2.1 对图 G，若 V(G)的子集 V′使得 )()( GwVGw >′?,则称 V′为图 G 的一个 顶点割集 。含有 k 个顶点的顶点割集称为 k－ 顶点割集 。
注,（ 1）割点是 1－顶点割集。
（ 2）完全图没有顶点割集。
定义 2.2.2 图 G 的 连通度 定义为 () min{| |GVVκ ′ ′= 是连通图 G 的顶点割集 }。特别地，
完全图的连通度定义为 1)(?=νκ
ν
K,空图的连通度定义为 0,不连通图的连通度定义为 0。
注,(1) 若 G 是平凡图，则 0)( =Gκ 。
(2) 使得 )(|| GV κ=′ 的顶点割集 V′称为 G 的 最小顶点割集 。
(3) 若 kG ≥)(κ,则称 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′使得 )()( GwEGw >′?,则称 E′为图 G 的一个 边割集 。含有 k 条边的边割集称为 k－边割集 。
注,(1) 对非平凡图 G，若 E′是一个边割集，则 EG ′\ 不连通。
(2) 一条割边构成一个 1－边割集。
(3) 设 )(GVS?,)(GVS?′,φ≠′SS,,记号 ],[ SS ′ 表示一端在 S 中另一端在 S′中的所有边的集合。对图 G 的每个边割集 E′，必存在非空的 )(GVS?,使得 ],[ SS 是 G 的一个边割集，其中 SVS \= 。
定义 2.2.4 图 G 的 边连通度 定义为 () min{| |GEEκ′ ′′= 是连通图 G 的边割集 }。完全图的边连通度定义为 1)(?=′ νκ
ν
K,空图的边连通度定义为 0，不连通图的边连通度定义为 0。
注,(1) 对平凡图 G,0)( =′ Gκ 。
(2) 是含有割边的连通图，则 1)( =′ Gκ 。
4
(3) 使得 )(|| GE κ′=′ 的边割集 E′称为 G 的 最小边割集 。
(4) 若 kG ≥′ )(κ,则称 G 为 k 边连通的 。
(5) 按上述定义，图 G 是 k 边连通的，当且仅当 G 的最小边割集至少含 k 条边，当且仅当 G 中没有 k?1 边割集，当且仅当从 G 中任意去掉 k?1 条边后，所剩图仍连通。
(6) 按照 k 边连通的定义,若图 G 是 k 边连通的,则它也是 k?1 边连通,k?2 边连通,…、
1 边连通的。因此，所有非平凡连通图都是 1 边连通的。
例如，下列图中,G
1
是连通的且有割点和割边，因此是 1 连通的和 1 边连通的； G
2
的最小点割集含 1 个点，最小边割集含 2 条边，故它是 1 连通的和 2 边连通的； G
3
的最小点割集和最小边割集分别含 2 个点和 2 条边，因此是 2 连通的和 2 边连通的； G
4
的最小点割集和最小边割集分别含 3 个点和 3 条边，因此是 3 连通的和 3 边连通的。
定理 2.2.1 )()()( GGG δκκ ≤′≤ 。
证明：先证 )()( GG κκ ′≤ 。
对图的边连通度 ()Gκ′ 作数学归纳法。
对 ()Gκ′ ＝ 1 的图 G，若
2
GK=,则显然 () 11Gκ υ′ =?=；若
2
GK≠,则 G 至少含三个点。设 e = uv 是 G 的一条割边，则 u 或 v 必是割点，故 ()Gκ =1。
总之，此时 ()Gκ = ()Gκ′ ＝ 1。
假设对所有 kκ′= 的图,都有 κκ′≤,则对 () 1Gkκ′ = + 的图 G,设 E是它的一个 1k +
边割集。任取边 ()euvEG=∈,则 Ee? 是 Ge? 的最小边割集，故 ()Ge kκ′?=。由归纳假设,()()Ge Geκκ′?≤?。取 Ge? 的最小点割集 T，则
||()()TGe Gekκκ′=?≤?=,
且 {}Tu∪ 构成 G 的最小点割集。 故 ()| {}|| |1 1 ()GTuT k Gκ κ′= ≤+≤+=∪ 。 归纳完成。
再证 )()( GG δκ ≤′ 。
设 δ=)(vd 。删去与 v 关联的 δ 条边后,G 变成不连通图，故这 δ 条边构成 G 的一个边割集。因此 )()( GG δκ ≤′ 。证毕。
下图 G
1
是一个 2,3κ κ′==和 4δ = 的图,G
2
是一个 1,2κ κ′= = 和 3δ = 的图。
G
1
G
2
G
3
G
4
G
1
G
2
5
定理 2.2.2 对具有 υ个顶点 ε 条边的连通图 G，有
2
()G
ε
κ
ν
≤
。
证明：因
()
2()
vVG
dvε δυ
∈
=≥
∑
，故
2ε
δ
υ
≤,由定理 2.2.1，
2ε
κδ
υ
≤≤ 。由于 κ 是整数，
因此
2ε
κ
ν
≤
。证毕。
定理 2.2.3 设 G 是一个简单图,k 是一个自然数，若
2
()
2
k
G
υ
δ
+?
≥,则 G 是 k 连通的。
证明：用反证法。假如 G 不是 k 连通的，则 G 的连通度 kκ <,即存在 G 的点割集 S，使得 ||Sk<,且 G?S 不连通。因 G?S 有 |S|υ? 个顶点，且至少有两个连通分支，故必有 G?S
的某个连通分支 G′含有不超过
|S|
2
υ?
个顶点。 注意到 G′中任一个顶点只可能与 G′内的点及 S 中的点相邻，因而其在 G 中的顶点度
|| |S|2
1| |
22
S
S
υ υ? +?
≤?+= 。结合 ||Sk<,
这意味着 (G)δ ≤
||2 2
22
Skυ υ+?+?
<,与定理条件矛盾。证毕。
推论 2.2.1 设 G 是一个简单图，若
1
()
2
G
υ
δ
≥,则 G 是连通的。
定理 2.2.4 设 G 是一个直径为 2 的简单图，则 (G) (G)κ δ′ = 。
证明：设 S 是 G 的一个最小边割集，则 G?S 有多于一个连通分支，取其中顶点数最少的一个记为 G
1
,G?S 的其余部分记为 G
2
。
如果 G
1
中存在顶点 u，它在 G 中不与 G
2
的顶点相邻，则对，由 (,) 2
G
duv= 知，在 G
中 v 有属于 G
1
的邻点。由此可知，在 G 中来看，要么 G
1
中每个点都在 G
2
中有邻点，要么
G
2
中每个点都在 G
1
中有邻点。在前一种情况下，
1
|S| (G )υ≥,在后一种情况下，
2
|S| (G )υ≥ 。总之，
12 1
|S| min{ (G ),(G )} (G )κυυυ′=≥ = 。 （ 1）
对
1
uG?∈,用
1
()du和
1
()du分别表示在 G 中 u 与 G
1
和 G
2
连的边数。则
12 1 2
( ) () () () ( ) 1 ()
G
Gdududu G duδ υ≤=+≤?+。
根据定理 2.2.1,
(G)κδ′≤≤
12
()1 ()Gduυ? + 。 （ 2）
结合（ 1）式可得
2
() 1du≥ 。 任取
01
()uVG∈,由于
110
2220120
| | () () ( ) ( ) 1 ( )
uG uG u
Sdu duduG duκυ
∈∈?
′== = + ≥?+
∑∑
,
结合（ 2）式得
6
120
()1 ()Gduυ?+ ≤ (G)κ δ′≤ ≤
120
()1 ()Gduυ? +
可见 (G)κδ′= 。证毕。
推论 2.2.2 设非空简单图 G 中任二不相邻顶点 u 和 v 都满足 () () 1du dv υ+ ≥?，则
(G) (G)κδ′ = 。
证明：若 G 中任意两点都相邻，则 G 是完全图,(G) 1 (G)κ υδ′ =?=,结论成立。若 G
中有不相邻顶点,则 diam 2G ≥ 。 但由于任二不相邻顶点 u和 v都满足 () () 1du dv υ+≥?，
即任二不相邻顶点 u 和 v 都有公共的邻点。因此又有 diam 2G ≤ 。从而 diam 2G = 。由定理 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－连通图。 （若只有两个顶点，则有反例，例如
2
K 是个块，但不是 2 连通的。 ）
关于 2 连通图（块）,有下列重要结论。
定理 2.3.1 (Whitney,1932) 3≥ν 的图 G 是 2－连通图（块）当且仅当 G 中任二顶点共圈。
证明：充分性：设 G 中任二顶点在同一圈上，欲证 G 是 2－连通的。
对 )(GVw∈?,任取 )(,wGVvu?∈ 。由条件,u,v 在 G 中共处于某个圈 C 上。若
Cw?,则在 wG \ 中 u,v 仍在圈 C 上；若 Cw∈,则 wG? 中 u,v 在路 wC? 上。总之
u,v 在 wG? 中有路相连。由 u,v 的任意性,wG? 是连通图，故 w 不是 G 的割点。再由 w
的任意性知,G 无割点，即 G 是 2－连通的。
7
必要性：设 G 是 2－连通图，欲证任二顶点 u,v 都在同一圈上。
对距离 ),( vud 作归纳法。
1),( =vud 时，因 2≥≥′ κκ,故 G 中无割边,uvG? 仍连通。因此 uvG? 中存在一条 ),( vu 路
1
P 。这表明在 G 中 u,v 都在圈 uvP +
1
上。
假定 kvud <),( 时，结论成立。下证 kvud =),( 时结论也成立。
当 kvud =),( 时，设 wvuP null=
0
是长为 k 的一条 ),( vu 路，则 1),(?= kwud 。由归纳法假设,u,w 在同一圈上，故在 u,w 间有两条无公共内部顶点的路 P 和 Q。因 G 是 2 连通图，故 wG? 仍连通。在 wG? 中存在 ),( vu 路 P′。令 x 是 P′上最后一个与 QP ∪ 的公共顶点（因 QPu ∪∈,这样的 x 存在） 。不妨设 Px∈,则 P 上 ),( xu 段＋ P′上 ),( vx 段与 wvQ + 是两条内部无公共点的 ),( vu 路。故 u,v 在同一圈上。归纳法完成。证毕。
推论 2.3.1 3≥ν 的图 G 是 2 连通图（块）当且仅当 G 中任二顶点被至少两条内部无公共顶点的路所连。
推论 2.3.2 若 3≥ν 的图 G 是 2 连通图（块）,则 G 的任二边都位于同一圈上。
证明：设 G 是 3≥ν 的 2 连通图，且 )(,
21
GEee ∈,在
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） 对 )(,GVvu ∈? 及 )(GEe∈?,存在 ),( vu 路含有边 e；
（ 6） 对 )(,,GVwvu ∈?,存在 ),( vu 路含有顶点 w;
（ 7） 对 )(,,GVwvu ∈?,存在 ),( vu 路不含有顶点 w。
证明,（ 1）?（ 2）见 Whitney 定理。
（ 2）?（ 3）设 G 中任二顶点共圈。对 )(GVu∈? 及 )(GExye ∈=?,若 ux = 或 uy =,
则结论显然。以下假定 uyx ≠,。设 C 是含 u 与 x 的圈。若 Cy∈,则 C 上含有 u 的 ),( yx
P
P
0
u
P′
v
Q
x
w
8
路与边 x y 形成一个圈，它含有 u 及边 e；
设 Cy? 。由 Whitney 定理,x 不是割点。故存在不含 x 的 ),( yu 路 P，令 w 是 P 上从 y
出发第一个与 C 公共的顶点，则 C 上 x-u-w 段＋ P 上 ),( yw 段＋ xy 构成一个含 u 和 e = xy
的圈。
（ 3）?（ 4）,与（ 2）?（ 3）类似可证。
（ 4）?（ 5）,设 G 中任二边共圈。对 )(,GVvu ∈? 及 )(GEe∈?,如果 uve =,结论显然成立；如果 u 或 v 之一是 e 的端点，比如 u 是 e 的端点而 v 的一个邻点是 w，则 e 与边
wv 共圈，故显然有 ),( vu 路含有边 e。
下面假定 u 和 v 都不是 e 的端点。
因任二边共圈显然任二点共圈，故由（ 2）?（ 3）知 u 与 e 共圈,v 也与 e 共圈。设这二圈分别是
1
C 和
2
C 。若
2
Cu∈ 或
1
Cv∈,则结论成立；若
2
Cu? 且
1
Cv?,则如下构作含 e 的 ),( vu 路：从 u 出发沿
1
C 到达
1
C 与
2
C 的第一个公共顶点 w，再从 w 出发沿
2
C 含 e
的部分到达 v，即可。
（ 5）?（ 6）,对 )(,,GVwvu ∈?,设与 w 相关联的一条边为 e。由（ 5）,存在 ),( vu 路含有边 e，于是含有 w。
x
u
y
u
vw
e
w
C
1
e
v
u
C
2
w
x
u
y
9
（ 6）?（ 7）,对 )(,,GVwvu ∈?,存在 ),( wu 路 P 含有顶点 v，则 P 的从 u 到 v 的一段不含有 w。
（ 7）?（ 1）,因为对 )(GVw∈? 及 )(,GVvu ∈?,存在 ),( vu 路不含有顶点 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)υ υ<,要么 (G) (H)υ υ= 且 (G) (H)ε ε≤ 。
下面证明该图 G 的四条结论。
（ 1）按照上述取法，由于 s(x,y) > 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| (,) 1sxy=?
且 U{}u∪ 和 U{}v∪ 都是 G 的 (x,y)分离集。
事实上，设 e = uv,H = G? e。 H 的 (x,y)分离数
s
H
(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)路的条数
(,)
H
rxy≤ r (x,y)≤ s(x,y)?1。 ()
10
由 G 的最小性可知,H 中的 (x,y)分离数等于 H 中两两内部点不交的 (x,y)路的最大条数，即
s
H
(x,y)= (,)
H
rxy。结合 (?)式和 ()式，知 s
H
(x,y)= (,)
H
rxy= s(x,y)?1。设 U 是 H 的一个最小 (x,y)分离集,由于 H 与 G 只相差一条边 e = uv,易见 U{}u∪ 和 U{}v∪ 都是 G 的 (x,
y)分离集。
（ 3）用 (),()
GG
NxNy表示 x 和 y 在 G 中邻点的集合，则 () ()
GG
Nx Ny φ=∩ 。
事实上，假如 () ()
GG
Nx Ny φ≠∩,则 u? ∈ () ()
GG
Nx Ny∩ 。设 HGu=?。由 G
的最小性,H 中 (x,y)分离数等于 H 中两两内部点不交的 (x,y)路的最大条数。与上述（ 2）的证明类似可知，图 H 的 (x,y)分离数 s
H
(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)。如果
12
{,,,}
k
Www w= null 是 G 的一个最小 (x,y)分离集，则
()
G
WNx? 或者 ()
G
WNy? 。
事实上,设 G
x
,G
y
为图 G W? 中分别包含 x 和 y 的连通分支,用
1
G 表示由 (G )
x
VW∪
在 G 中导出的子图，
2
G 表示由 (G )
y
VW∪ 在 G 中导出的子图。 显然
12
(G ) (G )VV W=∩ 。
如果
1
(G ) 1kυ =+，则 (G ) { }
x
Vx=,此时结论显然成立。同理，
2
(G ) 1kυ =+时结论成立。下面假设
1
(G ) 2kυ ≥+，且
2
(G ) 2kυ ≥+。给
1
G 添加一个新顶点 v*，将它与
1
G 中属于 W 的每个顶点都连新边，这样获得的图记为
1
G
。若
1
G
中存在 (x,v* )分离集 S 满足 | S
| < k，则易见 S 也是 G 的 (x,y)分离集，这与 G 的最小 (x,y)分离集 W 含 k 个点矛盾。由此可知，
1
G
的 (x,v* )分离数为 k。因
1
G
的阶小于 G 的阶，由 G 的最小性，
1
G
中任二点的分离数等于
1
G
中该两点间两两内部点不交路的最大条数。 因此
1
G
中有 k 条两两内部点不交的 (x,
v* )路。由
1
G
的结构可知，这 k 条路从 x 出发分别连到 W 的不同顶点。同理可知，从 y 出发也有 k 条两两不交的路分别连到 W 的不同顶点。这些路连接成 G 中 k 条两两内部点不交的 (x,y)路。这与 G 的取法矛盾。
现在继续完成定理的证明。
设 P 是 G 中一条最短的 (x,y)路。由结论（ 3）,P 的长至少为 3。设
12 t
Pxvv vy= null 。
按照结论（ 2）,存 在 G 的顶点子集 U，满足 |U| (,) 1sxy=? 且
1
U{}v∪ 和
2
U{}v∪ 都是 G
的 (x,y)最小分离集。由结论（ 1）,s(x,y) > 1，故 U φ≠ 。由结论（ 4）,
1
U{}v∪ ()
G
Nx?
或者
1
U{}v∪ ()
G
Ny?,但由于
1
()xvEG∈ 及结论（ ３ ）,可知 U()
G
Nx?,且
U? ()
G
Ny；同样，由结论（ 4）,
2
U{}v∪ ()
G
Nx? 或者
2
U{}v∪ ()
G
Ny?,但上面已知 U()
G
Nx?,由结论（ ３ ）可知必定
2
U{}v∪ ()
G
Nx?,从而
2
()
G
vNx∈ 。这与 P 是
G 的最短 (x,y)路矛盾。证毕。
由 Menger 定理可得到 Whitney 定理的如下推广
11
推论 2.4.1 1+≥ kν 的图 G 是 k 连通图当且仅当 G 中任二顶点至少被 k 条两两内部无公共顶点的路所连。
证明：必要性：用反证法。设 G 是 k 连通图。假定 G 中存在两个顶点 x,y，它们之间两两内部无公共顶点的路最多只有 m 条,m < k。分两种情况考虑。
(1) 如果 (G)xy E?,则因 G 中最小点割集的点数不超过 G 中最小 (x,y)分离集的点数，
由 Menger 定理,() (,)Gsxymkκ ≤=<。这与 G 是 k 连通图矛盾。
（ 2）如果 (G)xy E∈,则 H= G xy? 中两两内部无公共顶点的 (x,y)路最多只有
11mk?<?条。 由 Menger 定理,()(,)11
H
Gxy sxy m kκ? ≤=?<?。因此，存在
G xy? 的一个顶点子集 U,使得 |U| 2k≤?,且 (G ) Uxy 不连通。 故图 G(U{})x? ∪
和 G(U{})y? ∪ 中，至少有一个是不连通图，这表明 G 有不超过 k?1 个点的点割集，与 G
是 k 连通图矛盾。
充分性：用反证法。设 G 中任二顶点至少被 k 条两两内部无公共顶点的路所连。假如 G 不是 k 连通图，则 (G) kκ < 。设 W 是 G 的一个最小点割集，则 |W| (G) kκ= < 。从 GW?
的两个不同连通分支中各取一个点 x 和 y。由充分性的前提条件,x 和 y 在 G 中至少被 k 条两两内部无公共顶点的路所连，即 (,)rxy k≥ 。由 Menger 定理,G 中 (x,y)分离数 s(x,y)
= (,)rxy k≥,但因 |W| k<,故 x,y 在 GW? 中仍连通，这与 x,y 的取法矛盾。
证毕。
关于边连通有与 Menger 定理类似的结果，称为边形式的 Menger 定理。它的证明与
Menger 定理类似。
设 G 是一个简单图,x,y 是 G 中任二不同顶点。 如果从 G 中删去一组边后不再有 (x,y)
路则称这组边 分离 x 和 y，而称这组边为一个 (x,y)边分离集。 G 中含边数最少的 (x,y)边分离集称为 最小 (x,y)边分离集,其边数称为 G 的 (x,y)边分离数,记为 (,)sxy′ 。此外，将 G 中两两边不交的 (x,y)路的最大条数记为 (,)rxy′ 。
定理 2.4.2（边形式 Menger 定理）对任意图 G，设 x,y 是 G 中两个不相邻顶点，则 G 中分离 x,y 所需的最少边数等于 G 中两两边不交的 (x,y)路的最大条数，即 (,)sxy′ = (,)rxy′ 。
利用边形式 Menger 定理能够给出一个与推论 2.4.1 类似的边形式的结果，其证明与与推论 2.4.1 类似。
推论 2.4.2 图 G 是 k 边连通图当且仅当 G 中任二顶点至少被 k 条两两无公共边的路所连。
求图中点不交路和边不交路的算法可参看文献
N,Robertson,and P.D,Seymour,Outline of a disjoint paths algorithm,in Paths,Flows and
VLSI-Layout (B,Korte,L.Lovasz,H.J,Promel,and A,Schrijver editors),Springer-Verlag,Berlin,
1990,
J.M,Kleinberg,Approximation algorithms for disjoint paths problems,Ph.D thesis,MIT,
Cambridge,MA,May 1996,
12
A,Srinivasan,Improved approximations for edge-disjoint paths,unsplittable flow and related
routing problems,in Proc,38
th
Ann,Symp.on Foundations of Computer Science,1997,416-425,
S,G,Kolliopoulos,and C,Stein,Approximating disjoint-path problems using greedy algorithms
and packing integer programs,in Proceedings of 6
th
International IPCO Conference,Houston,
Texas,1998,
§ 2.5 可靠通信网络的设计
可靠网络设计问题,给定赋权图 G 和正整数 m，求 G 的具有最小权的 m 连通生成子图。
当 1=m 时，就是求最小生成树问题。
当 1>m 时，问题尚未解决。
当
n
KG = 且每边权皆为 1 时，问题成为：求
n
K 中边数最少的 m-连通生成子图。这一问题于 1962 年由 Harary 所解决。
令 ),( nmf 表示有 n 个顶点的 m 连通图所能具有的最少边数（ nm < ） 。设 G 是一个具有这种性质且有 ),( nmf 条边的图。因
∑
∈
=
)(
)(2
GVv
vdε,而 δκκ ≤′≤ 。故
),( nmf
22
)(
2
1
)(
mnn
vd
GVv
≥≥=
∑
∈
δ
。
Harary 找到了具有 n 个顶点、
2
mn
条边的 m 连通图。这种图记为
nm
H
,
，构造如下：
记
nm
H
,
的顶点集为 }1,,2,1,0{?nnull 。
（ 1） 若 m 为偶数，设 rm 2= 。当且仅当 )(mod20 nrrij ≤+?≤ 时，顶点 i 与 j 连边；
（ 2） 若 m 为奇数（设 12 += rm ）,而 n 是偶数，则先构作
2,rn
H,然后对
2
1
n
i ≤≤ 的
i，在顶点 i 与
2
n
i + 间加上一条边；
（ 3） 若 m 为奇数 （设 12 += rm ）,且 n 也是奇数,则先构作
nr
H
,2
,然后对
2
1
1
<≤
n
i
的 i，在顶点 i 与
2
1+
+
n
i 间加上一条边，再在顶点 0 与
2
1?n
,0 与
2
1+n
之间各加上一边。
H
4,8
(m=4,r=2,n=8) H
5,8
(m=5,r=2,n=8) H
5,9
(m=5,r=2,n=9)
3
2
1
0
5
4
7
6
5
2
1
0
4
3
7
6
8
3
2
1
0
5
4
7
6
13
定理 2.5.1
nm
H
,
是 m 连通的。
证明：只证 rm 2= 的情况。 12 += rm 的情况类似可证。
我们用反证法来证明
nm
H
,
中没有少于 rm 2= 个顶点的点割集。
若不然，设 V′是一个点割集且 rV 2|| <′ 。又设 i 与 j 是 VH
nr
′?
,2
中属于不同连通分支的两个顶点。考察顶点集
},1,,1,{ jjiiS?+= null 和 },1,,1,{ iijjT?+= null 。
这里加法取模 n。因 rV 2|| <′ 且 Vji ′?,，不失一般性，设 rVS <′|| ∩ 。则在 VS ′\ 中必存在一个始于 i 而终于 j，且任二相继项之差 r≤ 的序列。但由
nr
H
,2
的构成（ 1）,这样的序列中相邻项之间存在边。因此这个序列构成了 VH
nr
′\
,2
中一条 ),( ji 路。这与 i,j 的取法矛盾。证毕。
推论 2.5.1 ),( nmf ＝
2
mn
。
证明：容易检查 )(
,nm
Hε ＝
2
mn
。由上一定理，
nm
H
,
是 m 连通的，故
≤),( nmf =)(
,nm
Hε
2
mn
。
另一方面，前已述及 ≥),( nmf
2
mn
。故 ),( nmf ＝
2
mn
。证毕。
注,因 κκ ′≤,故
nm
H
,
也是 m 边连通的。若 ),( nmg 表示 n 个顶点的 m 边连通图可能的最少边数，则 ),( nmg ＝
2
mn
。
关于图的连通性和边连通性的更多内容可参看文献,
[1] J.A,Bondy,and U.S.R,Murty,Graph Theory with Applications,The Macmillan Press LTD,
1976.（中译本：吴望名、李念祖、吴兰芳、谢伟如、梁文沛译，图论及其应用，科学出版社,1984） 。
[2] D.B,West,Introduction to Graph Theory (second edition),Prentice-Hall,Inc.,(2001)149-190,
（中译本：李建中、骆吉周译，图论导引，机械工业出版社,2006） 。
[3]W.T,Tutte,Graph Theory,Cambridge University Press,(2001) 32-114.(影印版：图论，机械工业出版社,2004),
[4] D,Reinhard,Graph Theory (second edition),Springer-Verlag,New York,(2000)43-67,(影印版：图论，世界图书出版公司,2003),
[5] W,Mader,Connectivity and edge-connectivity in finite graphs,London Math,Lecture Note
Series,38(1979)66-95,
[6] J.C,Bermond,N,Homobono and C,Peyrat,Large fault-tolerant interconnection networks,
Graphs and Combinatorics,Springer,5(1989),107-123,
[7] D.F,Hsu,On container width and length in graphs,groups and networks,IEICE Trans,
14
Fundam,1994,E(77A),668-680,
[8] D.W,Matula,Determine edge connectivity in O(mn),Proc,28
th
Symp,On Foundations of
Computer Science,1987,249-251,
[9] J,Cheriyan,S,Vempala and A,Vatta,Approximation algorithms for minimum-cost k-vertex
connected subgraphs,Proceeding of the 34
th
Annual ACM Symposium on Theory of Computing,
Canada,2002,pp306-312,
[10] N,Lichiardopol,Broadcast time and connectivity,Discrete Applied Mathematics,143(2004),
359-363,
[11] T,Jordán,On minimally k-edge-connected graphs and shortest k-edge-connected Steiner
networks,Discrete Applied Mathematics,131(2003),421-432,
[12] P,Dankelmann and O,R,Oellermann,Bounds on the average connectivity of a graph,
Discrete Applied Mathematics,129 (2003),305-318,
[13] E,Oh and J,Chen,On strong Menger-connectivity of star graphs,Discrete Applied
Mathematics,129 (2003),499-511,
[14] J.Bang-Jensen,H,N,Gabow,T,Jordán,and Z,Szigeti,Edge-Connectivity Augmentation
with Partition Constraints,SIAM J,on Discrete Mathematics,12(1999),160-207,
[15] J,Cheriyan,A,Sebo,and Z,Szigeti,Improving on the 1.5-Approximation of a Smallest
2-Edge Connected Spanning Subgraph,SIAM J,on Discrete Mathematics,14(2001),170-180,
[16] T,Erlebach and K,Jansen,The Maximum edge-disjoint paths problem in bidirected trees,
SIAM J,on Discrete Mathematics,14(2001),326-355,
[17] D,Huygens,A,R,Mahjoub,and P,Pesneau,Two Edge-Disjoint Hop-Constrained Paths and
Polyhedra,SIAM J,on Discrete Mathematics,18(2004-2005),287-312
[18] H,N,Gabow,An Improved Analysis for Approximating the Smallest k-Edge Connected
Spanning Subgraph of a Multigraph,SIAM J,on Discrete Mathematics,19(2005),pp,1-18,
[19]G,Kortsarz,R,Krauthgamer,and J,R,Lee,Hardness of Approximation for
Vertex-Connectivity Network Design Problems,SIAM J,on Computing,33(2003-2004),704-720
[20] M,Katz,N,A,Katz,A,Korman,and D,Peleg,Labeling Schemes for Flow and Connectivity,
SIAM J,on Computing,34(2004-2005),23-40,
[21] 张先迪，李正良，图论及其应用，高等教育出版社,2005。
[22] 蒋长浩，图论与网络流，中国林业出版社,2001。
第二章习题
1,证明,若 G 是连通简单图但不是完全图,则 G 中必存在三个顶点 u,v 和 w,使得,uv vw E∈
而 uw E? 。
2,证明恰有两个顶点不是割点的简单连通图是一条路。
3,证明：点 v 是图 G 的割点当且仅当 v 至少属于 G 的两个不同的块。
4,证明或否定：如果直径为 2 的简单图有一个割点，则其补图有一个孤立顶点。
5,若一个图 G 至少有一条非环边，则 G 至少有两个非割点。
15
6,若 v 是简单图 G 的一个割点，则 Gv? 是连通的。
7,设 G 是自补图，证明,G 有割点当且仅当 G 有 1 度点。
8,证明：恰有两个顶点不是割点的简单连通图是一条路。
9,举反例说明下面的命题不成立,然后添加一个假设条件使其成立并证明所得命题的正确性：如果 e 是图 G 的一条割边，则 e 至少有一个端点是 G 的割点。
10,证明：若 G 的每个顶点均为偶度顶点，则 G 无割边。
11,证明顶点度全为偶数的图没有割边。对任意 1k ≥,构造具有一条割边的 21k + 正则简单图。
12,对于 2k ≥,证明：一个 k 正则二部图没有割边。
13,设 G 连通且 ()eEG∈ 。证明,e 在 G 的每棵生成树中当且仅当 e 是 G 的割边。
14,设 G 是一个图。
(1) 证明 G 是一棵树当且仅当它中连通的且其每条边都是割边；
(2) 证明 G 是一棵树当且仅当添加任一条以 ()VG中顶点为端点的边构成唯一一个圈。
15,证明：连通图 G 的一条边 e 是割边当仅且当 e 属于任何一棵生成树； e 是一个圈当且仅当 e 不属于任何一棵生成树。
16,令 C 是加权图中的一个圈，设 e 是 C 上权值最大的非割边，证明：存在一棵不包含 e
的最小生成树。由此证明：不断删除图中权值最大的非割边，直到剩下的图没有圈为止，最后将得到一棵最小生成树。
17,设 G 是一个直径为 2 的图,S 是 G 的一个最小边割集。证明,G－ S 的连通分支至少有一个同构于 K
1
或
(G)
K
δ
。
18,设 A,B 是两个集合，集合 (A B) (B A)∪ 称为 A 与 B 的对称差，记为 AB⊕ 。
证明,(1) AB⊕ = (A B) (A B)?∪∩； (2) 图 G 的两个边割集的对称差仍是 G 的边割集。
19,证明或否定：如果一个简单图 G 的最大度是
2
υ
，最小度是 1
2
υ
，则 G 是连通的。
20,证明：若 G 是简单图且其最小度 2δ≥ν?,则连通度 ()Gκ =δ。
21,对下面的每个图 G，确定其连通度、边连通度和最小顶点度。
22,构造一个连通度为 1 的 3 正则简单图。
23,证明：对图 G 的任一条边 e,(G ) (G) 1eκκ? ≥?。
24,证明：如果 G 是 3 正则简单图，则 (G) (G)κ κ′= 。
16
25,证明：若 G 是简单图且 (G) 3Δ≤，则 (G) (G)κ κ′= 。
26,设 H 是连通图 G 的子图。举例说明：有可能 (H) (G)κ κ> 。
27,设 G 是度至少为 2 的正则二部图，证明,(G) 1κ ≠ 。
28,一个单圈图是指仅含有一个圈的图。 (1) 证明：如果 G 是单圈图，则 (G) 2κ ≤ 且
(G) 2κ′ ≤ ； (2) 对所有单圈图 G 均有 (G) (G) 2κ κ′= = 吗？
29,证明或举反例,(1) 任何 k 连通图都是 k 边连通图； (2) 任何 k 边连通图都是 k 连通图。
30,证明：若 G 是 k 边连通的，则
2
k
ν
ε≥?。
31,证明：图 G 是 k 连通的当且仅当
n
GK∨ 是 k + n 连通的。这里
n
GK∨ 表示将 G 的每个顶点与完全图
n
K 的所有顶点都连边构成的图。
32,设 G 是连通图，且对其每条边 e，都存在两个包含 e 的圈 C
1
和 C
2
使得二者的唯一公共边为 e。证明 G 是 3 边连通的。由此证明 Peterson 图是 3 边连通的。
33,证明：连通图 G 是 k 边连通的当且仅当它的每个块都是 k 边连通的。
34,证明：图的每个顶点的度都是偶数当且仅当 G 的每个块都是欧拉图。
35,证明：若简单图 G 无偶圈，则 G 的每个块要么是 K
2
要么是奇圈。
36,证明：对不是块的连通图，至少有两个块，它们每个恰含有 G 的一个割点。
37,对非平凡连通图 G，定义 G 的块－割点图 B(G)为,B(G)的顶点集由 G 的所有块和割点组成,B(G)中两个顶点连边当且仅当一个是 G 的割点而另一个是 G 的包含该割点的块。
证明 B(G)是一棵树。
38,证明：若简单图 G 是一个 (G) 3δ ≥ 的块，则 G 中必存在顶点 v，使得 G v? 也是块。
39,设 G 是连通图并且其所有的块为 B
1
,B
2
,…,B
k
,证明 G 恰有 (() 1
k
i
ii
Bkυ
=
+
∑
个顶点。
40,设 G 是至少含有 3 个顶点的连通图，在 G 中距离为 2 的顶点对间全部添加新边，所得之图记为 G′。证明 G′是 2 连通的。
41,设 G 是一个连通图。 试给出一个公式,用 G 的块的生成树数目表示 G 的生成树的数目。
42,设 G 是一个块,x 和 y 是 G 的不同顶点。如果 P 是 G 中一条 (x,y)路，问 G 中是否一定存在一条与 P 内部点不交的路？
43,证明：图 G 是 2－边连通的当且仅当 G 的任二顶点至少由两条边不重的路所连。
44,设 G 是一个 k 连通图，
12
,,,
k
vv vnull 是 G 中 k 个不同的顶点。给 G 添加一个新顶点 w，
并将 w到上述 k个顶点都连上边,这样对 G修改之后所得之图记为 G′。 证明 (G ) kκ ′ = 。
45,设 G 是 k 连通图，且 H＝ G + K
1
(由完全图 K
1
的顶点向 G 的所有顶点连边构成之图 )，
17
证明 H 是 k+1 连通的。
46,设 G 是一个 k 连通图且 v 是 G 的一个顶点。对任意正整数 m，定义 G
m
是由 G 添加 m
个新顶点
12
,,
m
ww wnull 和所有形如,(1,( ))
iG
wu i m u N v≤ ≤∈ 的边后所得之图。证明
G
m
是 k 连通的。
47,证明或否定：如果 G 是一个 k 边连通图且 v,
12
,,
k
vv vnull 是 G 的 k+1 个不同顶点，那么对每个 1,2,,ik= null,都存在（ v,v
i
）路 P
i
,P
i
恰好包含 {
12
,,
k
vv vnull }中一个顶点 v
i
，
且当 ij≠ 时,P
i
和 P
j
是边不交的。
48,设图 G 满足,(G) 3κ =,且存在不相邻的顶点 x 和 y 使得 G 的 (x,y)分离数为 4。问,
（ 1）在 G 中内部点不交的 (x,y)路的最大数是多少？
（ 2）给出一个满足上述性质的图的例子。
49,证明：对任何图 G，有
2
(G)
ε
κ
υ
≤
及
2
(G)
ε
κ
υ
′ ≤
。
50,设图 G 是 k 连通的，证明必有 (G) kδ ≥ 。
51,设图 G 是 k 连通的，证明对 G 中任何一个顶点 v,G v? 是 k?1 连通的。
52,（ 1）设图 G 是 k 边连通的，且 k > 0，证明,若 E′是 G 的 k 条边的集合，则连通分支数 (G E ) 2w ′?≤；
（ 2）对 k > 0，找出一个 k 连通图 G 及 G 的 k 个顶点的子集 V′，使得 (G V ) 2w ′?>。
53,证明：若 G 是 k 边连通的，则
2
kυ
ε ≥ 。
54,（ 1）证明：若 G 是简单图且 (G) 2δ υ≥?，则 (G) (G)κ δ= 。 （ 2）找出一个简单图，
使得 (G) 3δ υ=?且 (G) (G)κδ< 。
