1
第七章 平面图
§ 7.1 平面图的概念
定义 7.1.1 如果图 G 能画在曲面 S 上，使得任意两边互不交叉，则称 G 可嵌入曲面 S。若图 G 可嵌入平面，则称 G 是 可平面图 或 平面图,画出的无交叉边的图形称为图 G 的 平面嵌入 。
例如,下面是三个平面图及其平面嵌入。
根据定义，下列定理是显然的。
定理 7.1.1 若图 G 是平面图，则 G 的任何子图都是平面图。
定理 7.1.2 若图 G 是非平面图，则 G 的任何母图都是非平面图。
定理 7.1.3 若图 G 是平面图,则在 G 中添加重边或环边后所得之图仍是平面图。
注,由以上定理知
(1) K
n
( n≤4 ) 和 K
1,n
(n ≥ 1)及其所有子图都是平面图。
(2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图 G 是简单图。
定义 7.1.2 设图 G 是平面图 (已平面嵌入 ),G 的边将平面划分出的若干区域都称为图 G 的面。其中面积无限的面称为 无限面 或外部面，面积有限的面称为 有限面 或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计 )，面 R 的次数记为 deg(R)。
定理 7.1.4 平面图 G 中所有面的次数之和等于 G 的边数的两倍，即
其中 R
1
,R
2
,
…
,R
r
是 G 的所有面。
证明,对 G 的任何一条边 e，若 e 是两个面 R
i
和 R
j
的公共边界，则在计算 R
i
和 R
j
的次数时,e 各提供了 1；若 e 只是某一个面的边界，则在计算该面的次数时,e 提供了 2。可见每条边在计算总次数时，都提供 2。因而结论成立。
1
deg( ) 2 ( ).
r
i
i
RGε
=
=
∑
2
定义 7.1.3 设 G 为简单平面图，若在 G 的任意不相邻的顶点 u,v 之间加边 uv
后，所得之图成为非平面图，则称 G 是极大平面图。
易见 K
1
,K
2
,K
3
,K
4
,K
5
– e 都是极大平面图。
定义 7.1.4 若非平面图 G 任意删除一条边后，所得之图都是平面图，则称 G 为极小非平面图。
容易证明下列定理
定理 7.1.5 极大平面图是连通的。
定理 7.1.6 n 阶（ n ≥ 3）极大平面图中没有割边和割点。
§ 7.2 欧拉公式
定理 7.2.1（欧拉公式） 设 G 是连通的平面图,n,m,r 分别是其顶点数、边数和
面数，则
n – m + r = 2。
证明,对边数 m 作数学归纳法。
当 m=0 时，因 G 是连通图，所以 G 只能是平凡图，结论显然成立。
假设当 m=k 时，结论成立。下面证明 m=k+1 的情况。
若 G 是树，则 G 至少有两片树叶。设 v 是 G 的一片树叶。令 G′ =G? v，则
G′ 仍是连通图,且 G′ 的边数 m′ =m?1=k,由归纳假设知,n′–m′ +r′ =2,而 n′ =n?1,
r′ =r,于是
n – m + r = (n′ +1) – (m′ +1) + r′ = n′–m′ +r′ = 2。
若 G 不是树，则 G 中含有圈。设边 e 在 G 的某个圈上。令 G′ =G? e，则 G′
仍是连通图，且 G′ 的边数 m′ =m?1=k,由归纳假设知
n′–m′ +r′ = 2,而 n′ =n,r′ =r?1,
于是 n – m + r = n′ – (m′ +1) + (r′+1) = n′–m′ +r′ = 2 。
证毕。
定理 7.2.2（欧拉公式的推广形式） 对于具有 w(w ≥ 1)个连通分支的平面图 G,有
n – m + r = w+1。
其中 n,m,r 分别是其顶点数、边数和面数。
证明,设 G 的连通分支分别为 G
1
,G
2
,
…
,G
w
，并设 G
i
的顶点数、边数和面数分别为 n
i
,m
i
,r
i
。由欧拉公式可知
3
定理 7.2.3 设 G 是连通的平面图，且每个面的次数至少为 l (l ≥ 3)，则 G 的边数
m 与顶点数 n 有如下关系,
(2).
2
l
mn
l
≤?
证明,由定理 7.1.4 可知
推论 7.2.1 K
5
和 K
3,3
都不是平面图。
证明,若 K
5
是平面图，由于 K
5
中无环边和重边，故每个面的次数至少为 3，
而 K
5
的边数为 10。由定理 7.2.3，应有,这是不可能的。因此 K
5
不是平面图。
若 K
3,3
是平面图，由于 K
3,3
中最短圈的长度为 4，故每个面的次数至少为
4，而 K
3,3
的边数为 9。由定理 7.2.3，应有,这是不可能的。
因此 K
3,3
不是平面图。证毕。
推论 7.2.2 K
n
(n ≥ 5)和 K
3,n
(n ≥ 3)都不是平面图。
证明,由定理 7.1.2 和推论 7.2.1 立即可知。
推论 7.2.3 K
5
和 K
3,3
都是极小非平面图。
由推论 7.2.1 和极小非平面图的定义容易验证。
定理 7.2.4 设 G 是具有 w(w≥1)个连通分支的平面图,各面的次数至少为 l(l ≥3)，
则 G 的边数 m 与顶点数 n 有如下关系,
证明,利用欧拉公式的推广形式 (定理 7.2.2)，与上一定理类似可证。
11
1
1111
2,( 1,2,).
,.,,
1,
2( ) 1
iii
ww
ii
ii
w
i
i
wwww
iii i i i
nmr i w
mmnn G G
Grrw
wnmr nmrnmrw
==
=
====
+= =
=?+
=?+=?+=?++?
∑∑
∑
∑∑∑∑
null
易知 由于 的每个分支有一个外部面 而 只有一个外部面故 的面数 于是整理即得结论,证毕.
1
2deg()
2.,2(2),
r
i
i
mRlr
rmn mlmn
=
=≥?
=+? ≥ +?
∑
由欧拉公式可知 将此式代入上式 得 整理便得结论。证毕。
3
10 (5 2) 9
32
≤?=
4
9(62)8
42
≤?=
(1).
2
l
mnw
l
≤
4
定理 7.2.5 设 G 是具有 m 条边的 n(n≥3) 阶简单平面图，则 m ≤ 3n?6 。
证明,设 G 有 w (w≥1) 个连通分支。若 G 为树或森林，则 m = n? w ≤ 3 n? 6 。
否则,G 中必有圈。因 G 是简单图，所以各圈的长度至少是 3，从而 G 中面的最小次数 l ≥ 3 。又因函数
在 l=3 时达到最大值 3，于是由定理 7.2.4,
证毕。
定理 7.2.6 具有 m 条边的 n(n ≥ 3) 阶简单连通的平面图 G 是极大平面图当且仅当 G 的每个面的次数均为 3。
证明,充分性,由定理 7.1.4 知,。因 G 是连通的，由欧拉公式可知,r =2+m–n。由此二式整理得,m =3n–6 。
假如 G 不是极大平面图，则 G 中一定存在不相邻的顶点 u 和 v，使得 G′
=G+uv 仍是简单平面图，而 G′ 的边数 m′ =m+1,n′ =n,结合 m =3n–6 得,m′ =
3n′ – 5> 3n′ – 6 。这与定理 7.2.5 矛盾。
必要性 设 G 是简单、连通的极大平面图，则 G 中无环边和重边，且由定理
7.1.6 可知,G 中无割边和割点。于是 G 中各面的次数至少为 3。以下用反证法证明 G 中各面的次数不会大于 3。从而使必要性得证。
事实上，假如 G 的某个面 R
i
的次数 deg(R
i
)=s ≥ 4，则 R
i
的边界上至少有 4
个顶点，设其中 4 个依次相邻的顶点为 v
1
,v
2
,v
3
,v
4
。若 v
1
与 v
3
在 G 中不相邻，
则在 R
i
内添加边 v
1
v
3
不破坏平面性，这与 G 是极大平面图矛盾。因而 v
1
与 v
3
在 G 中必定相邻。但因面 R
i
的存在，边 v
1
v
3
必在 R
i
的外边。类似地,v
2
与 v
4
在
G 中也必定相邻且边 v
2
v
4
必在 R
i
的外边。于是边 v
1
v
3
与边 v
2
v
4
必在 R
i
的外部相交。这与 G 是平面图矛盾。从而 G 中各面的次数不会大于 3。 证毕。
由该定理可知，下列平面图中，只有 (c)是极大平面图。
2
1
22
l
ll
=+
(1)3(2)36.
2
l
mnwnn
l
≤≤?=?
1
2deg()3
r
i
i
mRr
=
= =
∑
(a)
(c)
(b)
5
定理 7.2.7 设 G 是具有 m 条边的 n (n ≥ 3) 阶极大平面图，则 m=3n–6。
证明,由于极大平面图是连通图，由欧拉公式,r=2+m–n。 又因 G 是极大平面图，由定理 7.2.6 可知,G 的每个面的次数均为 3，故
由以上两式整理即得,m=3n–6 。证毕。
定理 7.2.8 设 G 是具有 m 条边的 n (n ≥ 3) 阶简单平面图，则 G 的最小度 δ ≤ 5。
证明,若 G 的阶数 n ≤ 6,则结论显然成立，下设 n ≥ 7 。假若 δ ≥ 6，则
因而 m ≥ 3n，这与定理 7.2.5 矛盾。证毕。
§ 7.3 平面图的判断
定义 7.3.1 设 e = uv 是图 G 的一条边。在 G 中删除 e，并添加新点 w，令 u 和 v
均与 w 相邻，这个过程称为在G中插入2度顶点w；反之，设 w 为 G 中一个 2
度顶点，设它的两个邻点为 u 和 v，删除 w 并添加新边 uv，这个过程称为在G
中消去2度顶点w。
定义 7.3.2 若两个图 G
1
和 G
2
同构，或者 G
1
和 G
2
经过反复插入或消去 2 度顶点后同构，则称 G
1
和 G
2
是 同胚的 。
例如，下列 (a)与 K
3
同胚,(b)与 K
4
同胚。
下列两个定理是平面图判定定理，证明从略。
定理 7.3.1 (库拉托夫斯基定理 1) 图 G 是平面图当且仅当 G 中既不含与 K
5
同胚的子图，也不含与 K
3,3
同胚的子图。
定理 7.3.2 (库拉托夫斯基定理 2) 图 G 是平面图当且仅当 G 中既没有可收缩到
K
5
的子图，也没有可收缩到 K
3,3
的子图。
1
2deg()3
r
i
i
mRr
=
==
∑
1
2()6.
n
i
i
mdvn
=
=≥
∑
(b) (a)
6
§ 7.4 平面图的对偶图
定义 7.4.1 设 G 是平面图的某个平面嵌入,G 的对偶图G* 构造如下,
在 G 的面 R
i
中放置 G* 的顶点 v
i
*。设 e 为 G 的任意一条边，若 e 在 G 的面 R
i
与 R
j
的公共边界上，做 G* 的边 e*与 e 相交，且 e* 关联 G* 的位于 R
i
和 R
j
中的顶点 v
i
*与 v
j
*，即 e*= v
i
*v
j
*,e* 不与其它任何边相交。若 e 为 G 中的割边且在面 R
i
的边界上，则 e*是以 R
i
中 G* 的顶点 v
i
*为端点的环，即 e* = v
i
*v
i
* 。
简单的说，平面图 G 的对偶图G* 就是以 G 的面作为顶点的图：用顶点代表 G 的各个面，两个面有 k 条公共边界，则相应的顶点间连 k 条边。若某个面中含有割边，则该面相应的点上连一条环边。
从定义不难看出 G 的对偶图 G* 有以下性质,
(1) G* 是平面图，而且是平面嵌入。
(2) G*是连通图。
(3) 若边 e 为 G 中的环边，则 G* 与 e 对应的边 e* 为割边；反之，若 e 为割边，则 G* 中与 e 对应的边 e* 为环边。
(4) 在多数情况下,G*为含重边的图。
(5) 同构的平面图（平面嵌入）的对偶图不一定是同构的。
例如,下列两图（实线边的图）是同构的，但它们的对偶图（虚线所示）
不同构，因为两个对偶图中环边所关联的顶点的度不相等,
平面图 G 与它的对偶图 G*的顶点数、边数和面数有如下关系。
定理 7.4.1 设 G*是连通平面图 G 的对偶图,n*,m*,r* 和 n,m,r 分别为 G*和 G
的顶点数、边数和面数,则
(1) n* = r; (2) m* = m; (3) r* = n ;
(4) 设 G*的顶点 v
i
* 位于 G 的面 R
i
中，则 d
G′
(v
i
* )=deg(R
i
)。
证明,由 G* 的构造可知,(1)和 (2)是显然的。
(3) 由于 G 与 G* 都连通，因而满足欧拉公式,
n－ m＋ r = 2,n*－ m*＋ r* = 2
7
由此及上述（ 1）、（ 2），便得
(4) 设 G 的面 R
i
的边界为 C
i
。设 C
i
中有 k
1
条割边 (k
1
≥0),k
2
条非割边，则 C
i
的长度为 k
2
+2k
1
,即 deg(R
i
) = k
2
+2k
1
。与 G 中这 k
1
条割边对应，在 G* 中 v
i
*处有 k
1
个环边，而 C
i
的 k
2
条非割边对应 G* 中从 v
i
* 处引出 k
2
条边，所以
定理 7.4.2 设 G
*
是具有 w 个连通分支的平面图 G 的对偶图,
则 (1) n* = r ;
(2) m* = m;
(3) r* = n－ w＋ 1;
(4) 设 v
i
* 位于 G 的面 R
i
中，则 d
G*
(v
i
* )=deg(R
i
)。
其中 n*,m*,r*,n,m,r 同前。
证明留作练习。
§ 7.5 平面图的面染色和四色猜想
一、平面图的面染色
定义 7.5.1 平面图的平面嵌入 G 的 面正常 k 染色 （ proper face k- colouring）是指
k 种颜色 1,2,,knull 在 G 的面集合 F(G)上的一种分配，使得有公共边的面所染颜色不同。用映射的观点看,G 的面正常 k 染色是一个映射
:(){1,2,,}cFG k→ null,
使得对每个 i ( ki,,2,1 null= ),)(
1
ic
内的面两两无公共边。
注,若令
1
() { ( ) ( ) },( 1,2,,)
i
F ci f FGcf i i k
==∈ ==null,则 G 的一个面正常 k
染色可看成是对面集合的一种划分
12
(,,,)
k
cFF F= null,其中每个 F
i
中的面彼此不相邻（无公共边）。
定义 7.5.2 若平面图的平面嵌入 G 存在一种面正常 k 染色，则称 G 是 面 k 色可染的 （ face k-colourable）。
定义 7.5.3 正整数 () min{GkGχ
= 面 k 色可染的 }称为 G 的 面色数 (face
chromatic number)。
例如,
4
()4Kχ
= 。
22.rmnmrn
=+? =+?=
*
*
21
() 2 deg().
ii
G
dv k k R=+ =
8
定理 7.5.1 设 G
是 G 的对偶图，则 (G) (G )χχ
= 。
证明,由定义立即可知。
四色猜想,任何地图只需用 4 种颜色来染色，就可使得任何具有公共边界的两个区域染不同的颜色 。
四色猜想的图论表述,对任何平面图的平面嵌入 G,(G) 4χ
≤ 。
二、四色猜想的几种等价表述
定理 7.5.2 对任何平面图 G,(G) 4χ ≤ 当且仅当其色多项式 (,4) 0PG > 。
证明,由色数和色多项式的定义立即可知。
定理 7.5.3 下列三个命题等价,
（ 1） 每个平面图都是点 4 可染的；
（ 2） 每个平面图的平面嵌入是面 4 可染的；
（ 3） 每个简单 2 边连通 3 正则平面图是边 3 色可染的。
证明,（ 1）?（ 2）设 G 是某平面图的一个平面嵌入,G
是其对偶图。则 G
也是平面图。由（ 1）,G
是点 4 色可染的。这种点 4 染色对应有 G 的一个 4
色正常面染色。
（ 2）?（ 3）设 G 是简单 2 边连通 3 正则平面图,G
null
是其一个平面嵌入。由 (2),
G
null
有面正常 4 染色? 。用
012 3
c (0,0),c (0,1),c (1,0),c (1,1)====来表示四种颜色。构造 G
null
的一种边染色如下,
对于边 ()eEG∈
null
，若 e 是某两个面,f g 的公共边且,f g 在? 下的颜色分别为,
ij
cc，则给 e 染颜色 () (mod2)
ij
Ce c c=+,
其中 c
i
与 c
j
的加法是向量相加，对各分量分别模 2。由于 G（从而 G
null
）是 2 边连通的，故 G
null
中每条边 e 都必定是某两个面的公共边，即 G
null
的每条边都被染色，并且这种染色只用到颜色 c
1
,c
2
,c
3
[因 c
0
,c
1
,c
2
,c
3
中不同的向量两两作加法 (模 2)只能得到 c
1
,c
2
,c
3
]。此外，由于 G
null
是 3 正则的，故每个顶点 u 关联
3 条边，设这 3 条边所夹的三个面的色为 c
i
,c
j
,c
k
（互不相同），则按边的染色规则，这 3 条边应分别染上色 c
i
+ c
j
,c
j
+ c
k
,c
k
+c
i
，这是三种不同的色。可见相邻的三边必染不同的色。因此 C 是 G
null
的一种正常的边 3 染色。
（ 3）?（ 1）假设（ 3）成立。下面用反证法证明（ 1）。
9
若存在一个平面图 G 不能用 4 种色正常染色，则其色数至少为 5。设 G
null
是
G 的一个平面嵌入，则存在一个三角剖分图 H，使得 G
null
是 H 的生成子图（留作习题）,H 的对偶图 H
是 2 边连通 3 正则的简单图（留作习题）。由（ 3），
H
是边 3 色可染的。设
123
(,,)cEEE= 是 H
的一个边正常 3 染色。对于 ij≠,
设 [],
ij i j
HHEE
=∪（只有
12 13 23
H,H,H三种）。因 H
中每个顶点都是 3 度的，故染色 c 的每种颜色都在 H
的每个顶点处出现，因而
ij
H
的每个顶点都是 2
度的，这样的图是边不相交的圈的并。
容易证明此时
ij
H
是面 2 色可染的。令
112 213
(){,} (){,}FH FH? αβ? γδ
→→：；,
分别是
12
H
和
13
H
的正常面 2 染色。于是 H
的每个面是
12
H
的某个面与
13
H
的某个面的交集的一部分。所以在
12
和下，面 f 获得两种颜色 x 和 y,记为 (x,y),
其中 xyα βγδ==或，或。定义四种新的颜色 (,),(,),(,),(,)α γαδβγβδ。易见
H
的每个面被这四种颜色之一所染。由于
12 13
HH H
= ∪,而且 H
的相邻两个面得到的颜色对不会相同，所以得到了 H
的一个面正常 4 染色。因 G
null
是 H 的生成子图，故 5(G)(G)(H) (H)4χχχχ
==≤= ≤
null
，这是不可能的。
这两个定理给出了四色猜想的四种等价表述,
(1) 面染色表述：对任何平面图的平面嵌入 G,(G) 4χ
≤ 。
(2) 点染色表述：对任何平面图 G,(G) 4χ ≤ 。
(3) 边染色表述：每个简单 2 边连通 3 正则平面图是边 3 色可染的。
(4) 色多项式表述：对任何平面图 G，色多项式 (,4) 0PG > 。
3
1
1
3
3 3
2 2
2
1
2
1
H
*
H
*
12
1
1
22
2
1
2
1
f
2
f
3
f
1
(,)α γ (,)β γ
(,)α δ
10
三、五色定理
定理 7.5.4 (五色定理,Heawood,1890) 对于任何平面图 G,(G) 5χ ≤ 。
证明,因为重边不影响点色数，故无妨设图 G 是平面简单图。对顶点数 ν 作数学归纳。
5ν ≤ 时，定理结论显然成立。
假设对 1nν ≤?的所有平面图，定理结论都成立。考虑 nν = 的情形。
由定理 7.2.8，存在
00
() () 5vVG dv∈≤，使得 。
（ 1）若
0
() 4dv ≤,考虑 G?v
0
。由归纳假设，
0
()5Gvχ? ≤ 。再给 v
0
染上与其邻点（不多于四个）相异的第五种色即可。
（ 2）若
0
()dv = 5,设 v
1
,v
2
,v
3
,v
4
,v
5
是 v
0
的邻点。将它们按逆时针顺序画在平面上，记 G
0
= G?v
0
。由归纳假设,G
0
可用五种色正常染色。设顶点 v
1
,v
2
,
v
3
,v
4
,v
5
在 G
0
中分别染以色 a,b,c,d,e。可以假定这五种色互不相同（如果 v
1
,
v
2
,v
3
,v
4
,v
5
中有染相同色的顶点，则可用第五种色给 v
0
染色）。用 G
ac
表示 G
0
中染 a 色和染 c 色的顶点导出的子图。
i）若 v
1
与 v
3
分别在 G
ac
的两个连通分支中，则在含有 v
1
的连通分支中将颜色 a,c 互换，这样便可给顶点 v
0
染色 a，从而得到 G 的一个点正常 5 染色。
ii）若 v
1
与 v
3
在 G
ac
的同一个连通分支中，则存在一个 (v
1
,v
3
)路 P，在 P 上顶点的色 a,c 交替出现。从图 G 中来看,v
0
v
1
+P+ v
3
v
0
是一个圈。由于 G 已嵌入平面，故 v
2
与 v
4
必分别处在该圈的内、外，因此在 G
0
中由 b,d 两色导出的子图 G
bd
中,v
2
与 v
4
分属于两个连通分支。（否则，在 G
bd
中有 (v
2
,v
4
)路 Pˊ,
它与路 P 相交于一个公共顶点 u，由于 u 在 Pˊ上，故应染有颜色 b 或 d,u 也在 P 上，又应染有颜色 a 或 c，这是不可能的）。无妨设 v
2
处在圈内，这时可将 v
2
所在的连通分支中 b 色与 d 色对换，再给 v
0
染上颜色 b，这样便可得到 G
的一个点正常 5 染色。证毕。
b
v
2
v
0
v
3
v
4
v
5
a
c
d
e
v
1
11
四、四色猜想简介
1852 年，英国学生 Francis Guthrie 在给英国地图染色时发现，只需要四种颜色就可以将相邻的区域区分开。于是向他的哥哥 Frederick Guthrie 提出如下猜想,任何地图只需用 4 种颜色来染色，就可使得任何具有公共边界的两个区域染不同的颜色 。
Frederick 转而请教他的老师、当时伦敦大学数学教授 A.De Morgan,A.De
Morgan 后来又写信将此猜想告诉给爱尔兰数学家 W,R,Hamilton。起初，这个问题并未引起人们的注意，但经过一段时间尝试之后，大家发现这个猜想并不容易被证明或被否定。 1878 年，当时伦敦数学会负责人 A,Cayley 向伦敦数学会成员正式公布了这个猜想。于是形成了著名的四色猜想。
z Kempe 给出的“证明”。
每个有界面都为 3 次面的平面图称为 构形 (configuration)。例如，下列四个平面图都是构形。
设 F 是由有限个构形组成的集合，若任何三角剖分平面图至少含有 F 中一个构形，则称 F 是 不可免完备集 （ unvoidable complete set）。
由定理 7.2.8，每个简单平面图的最小度≤ 5，从而任何三角剖分平面图的最小度也不超过 5，故上列四个构形组成的集合 F={O,P,Q,R}是一个不可免完备集。
如果有简单平面图 G 使得 (G) 5χ =,但对任何阶数小于 (G)ν 的平面图 H
均有 ()4Hχ ≤ 则称 G 是 极小图 (minimal graph)。根据 5 色定理可知，若四色猜想不真，则必存在极小图。
1879 年,Kempe 给出了四色猜想的第一个“证明”。他企图通过证明极小图不存在来证明四色猜想。“证明”使用反证法，思路如下。
若存在极小图 G，则易证 G 是一个三角剖分图，从而它必含有 F={O,P,Q,
R}中的构形。
若 G 含有构形 O 或 P，则由反证法假设,()4Gvχ? ≤ （ v 为构形的中心点）。设 π =(V
a
,V
b
,V
c
,V
d
)是图 G?v 的一个正常点 4 染色。则在染色 π 下,v 的
v
v
v v
P Q
O R
12
邻点集 N
G
(v)至多只需用到 3 种色，因而 4 色中可有一种色给点 v 染色，可见 π
也是图 G 的正常点 4 染色，这与 (G) 5χ = 矛盾。
若 G 含有构形 Q，则由反证法假设,()4Gvχ? ≤ (v 为构形 Q 的中心点 )。
设 π =(V
a
,V
b
,V
c
,V
d
)是图 G?v 的一个正常点 4 染色，并设 N
G
(v)={v
1
,v
2
,v
3
,v
4
}。
无妨假定
1234
,,,
abcd
vVvVvVvV∈∈∈∈，则 v
1
,v
4
在导出子图 G
ad
=G[V
a
∪ V
d
]中以及 v
2
,v
3
在导出子图 G
bc
=G[V
b
∪ V
c
]中不可能同时都是连通的（否则 G
ad
中
v
1
v
4
路与 G
bc
中 v
2
v
3
路会相交）。无妨设 v
1
和 v
4
在 G
ad
中不连通。这时交换 G
ad
中含 v
1
的连通分支中顶点的颜色，则 v
1
被染上色 d，而 v
2
,v
3
,v
4
的色不变。
因此可用色 a 来给点 v 染色，这样得到图 G 的一个正常点 4 染色，这又与
(G) 5χ = 矛盾。
Kempe 采用同样的方法“证明”了 G 也不可能含有构形 R，从而与 F 是不可免完备集矛盾。这样便“证明”了极小图不存在，四色猜想成立。
1890 年,P,J,Heawood 举出一个反例说明上述证明中 G 不含构形 R 的结论并非总能成立。从而否定了 Kempe 的证明。
z 寻找可约构形的不可免完备集。
设 S 是一个构形，若它不含在任何极小图中，则称 S 为 可约的 (reducible)。
Kempe 实际上证明了 O,P,Q 是可约的，但并没有证明 R 也是可约的。
尽管如此,Kempe 的证明提供了一条证明四色猜想的途径：寻找一个由可约构形组成的不可免完备集。
1904 年,P,Wernicke 找到一个新的不可免完备集（图 1）。
1913 年,G,D,Birkhoff 找出另一个不可免完备集（图 2）。
但他们都不能证明其中最后两个构形是可约的。
图 1
图 2
13
1913 年,G,D,Birkhoff 又发现了一个新的可约构形（图 3）。
此后，人们陆续发现了数千个可约构形。
1960 年,H,Heesch 试图用计算机在已发现的可约构形中找出不可免完备集，并提出一个判断给定的构形集合是否为不可免完备集的算法。
1961 年,Y,Shimamoto 宣布找到了一个由可约构形组成的不可免完备集。
但 Whitney 和 Tutte 在 1972 年发现 Shimamoto 在利用计算机判断时误算了一个构形的可约性。同时，他们提出了构形可约性分类理论。
1976 年,Apple 和 Haken 与 Koch 合作改进了 Heesch 的算法，并研究了可约构形的范围，最后利用计算机花了 1260 个机时，找到了一个由 1936 个可约构形组成的不可约完备集，从而宣布证明了四色猜想。
z Tait 的“证明”
值得提出的是,P.G,Tait 在 1880 年断言：每个 3 正则 3 连通平面图都是
Hamilton 图。在这个假设下他给出了四色猜想的一个证明。 60 多年后，
W.T.Tutte 于 1946 年构造出一个 3正则 3 连通非 Hamilton 平面图，从而否定了
Tait 的证明。
有关四色问题的更多内容可参看 [1]与 [2]，有关平面图的进一步了解可参看文献 [3]。
[1] D.R,Woodall and R.J,Wilson,The Appel-Haken proof of the four-color theorem,
Selected Topics in Graph Theory (eds,L,W,Beineke,and R.J,Wilson),Academic
Press,London,(1978) 83-101,
[2] R.C,Read,Some applications of computers in graph theory,Selected Topics in
Graph Theory,(eds,L,W,Beineke,and R.J,Wilson),Academic Press,New York,
(1978) 417-444,
[3] T,Nishizeki,and N,Chiba,Planar graphs,Theory and Algorithms,North-
Holland,Amsterdam,1988,
图 3
14
第七章习题
1.证明,(1) K
5
– e 是平面图； (2) K
3,3
– e 是平面图,
2,证明：不存在这样的平面图,它有 5 个面，且任二面间均至少有一条公共边。
3,(1) 证明：若 G 是围长 的连通平面图，则 。
(2)利用 (1)的结论证明,Peterson 图是非平面图。
4,证明每个平面图都是点 6 色可染的。
5,每个面的次都是 3 的平面图称为三角剖分平面图。证明顶点数至少为 3 的每个简单平面图都是某个三角剖分平面图的生成子图,
6,设 G 是至少含 4 个顶点的三角剖分简单平面图。证明其对偶图 G
*
是简单 2 边连通 3 正则平面图。
7,证明,设 G 是无割边的连通平面图,(G) 2ν ≥ 。证明,G 的平面嵌入是面 2 色可染的当且仅当 G 是 Euler 图。
8,证明,每个 Hamilton 平面图的平面嵌入都是面 4 色可染的。
3k ≥
(2)
2
k
k
ν
ε
≤
第七章 平面图
§ 7.1 平面图的概念
定义 7.1.1 如果图 G 能画在曲面 S 上，使得任意两边互不交叉，则称 G 可嵌入曲面 S。若图 G 可嵌入平面，则称 G 是 可平面图 或 平面图,画出的无交叉边的图形称为图 G 的 平面嵌入 。
例如,下面是三个平面图及其平面嵌入。
根据定义，下列定理是显然的。
定理 7.1.1 若图 G 是平面图，则 G 的任何子图都是平面图。
定理 7.1.2 若图 G 是非平面图，则 G 的任何母图都是非平面图。
定理 7.1.3 若图 G 是平面图,则在 G 中添加重边或环边后所得之图仍是平面图。
注,由以上定理知
(1) K
n
( n≤4 ) 和 K
1,n
(n ≥ 1)及其所有子图都是平面图。
(2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图 G 是简单图。
定义 7.1.2 设图 G 是平面图 (已平面嵌入 ),G 的边将平面划分出的若干区域都称为图 G 的面。其中面积无限的面称为 无限面 或外部面，面积有限的面称为 有限面 或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计 )，面 R 的次数记为 deg(R)。
定理 7.1.4 平面图 G 中所有面的次数之和等于 G 的边数的两倍，即
其中 R
1
,R
2
,
…
,R
r
是 G 的所有面。
证明,对 G 的任何一条边 e，若 e 是两个面 R
i
和 R
j
的公共边界，则在计算 R
i
和 R
j
的次数时,e 各提供了 1；若 e 只是某一个面的边界，则在计算该面的次数时,e 提供了 2。可见每条边在计算总次数时，都提供 2。因而结论成立。
1
deg( ) 2 ( ).
r
i
i
RGε
=
=
∑
2
定义 7.1.3 设 G 为简单平面图，若在 G 的任意不相邻的顶点 u,v 之间加边 uv
后，所得之图成为非平面图，则称 G 是极大平面图。
易见 K
1
,K
2
,K
3
,K
4
,K
5
– e 都是极大平面图。
定义 7.1.4 若非平面图 G 任意删除一条边后，所得之图都是平面图，则称 G 为极小非平面图。
容易证明下列定理
定理 7.1.5 极大平面图是连通的。
定理 7.1.6 n 阶（ n ≥ 3）极大平面图中没有割边和割点。
§ 7.2 欧拉公式
定理 7.2.1（欧拉公式） 设 G 是连通的平面图,n,m,r 分别是其顶点数、边数和
面数，则
n – m + r = 2。
证明,对边数 m 作数学归纳法。
当 m=0 时，因 G 是连通图，所以 G 只能是平凡图，结论显然成立。
假设当 m=k 时，结论成立。下面证明 m=k+1 的情况。
若 G 是树，则 G 至少有两片树叶。设 v 是 G 的一片树叶。令 G′ =G? v，则
G′ 仍是连通图,且 G′ 的边数 m′ =m?1=k,由归纳假设知,n′–m′ +r′ =2,而 n′ =n?1,
r′ =r,于是
n – m + r = (n′ +1) – (m′ +1) + r′ = n′–m′ +r′ = 2。
若 G 不是树，则 G 中含有圈。设边 e 在 G 的某个圈上。令 G′ =G? e，则 G′
仍是连通图，且 G′ 的边数 m′ =m?1=k,由归纳假设知
n′–m′ +r′ = 2,而 n′ =n,r′ =r?1,
于是 n – m + r = n′ – (m′ +1) + (r′+1) = n′–m′ +r′ = 2 。
证毕。
定理 7.2.2（欧拉公式的推广形式） 对于具有 w(w ≥ 1)个连通分支的平面图 G,有
n – m + r = w+1。
其中 n,m,r 分别是其顶点数、边数和面数。
证明,设 G 的连通分支分别为 G
1
,G
2
,
…
,G
w
，并设 G
i
的顶点数、边数和面数分别为 n
i
,m
i
,r
i
。由欧拉公式可知
3
定理 7.2.3 设 G 是连通的平面图，且每个面的次数至少为 l (l ≥ 3)，则 G 的边数
m 与顶点数 n 有如下关系,
(2).
2
l
mn
l
≤?
证明,由定理 7.1.4 可知
推论 7.2.1 K
5
和 K
3,3
都不是平面图。
证明,若 K
5
是平面图，由于 K
5
中无环边和重边，故每个面的次数至少为 3，
而 K
5
的边数为 10。由定理 7.2.3，应有,这是不可能的。因此 K
5
不是平面图。
若 K
3,3
是平面图，由于 K
3,3
中最短圈的长度为 4，故每个面的次数至少为
4，而 K
3,3
的边数为 9。由定理 7.2.3，应有,这是不可能的。
因此 K
3,3
不是平面图。证毕。
推论 7.2.2 K
n
(n ≥ 5)和 K
3,n
(n ≥ 3)都不是平面图。
证明,由定理 7.1.2 和推论 7.2.1 立即可知。
推论 7.2.3 K
5
和 K
3,3
都是极小非平面图。
由推论 7.2.1 和极小非平面图的定义容易验证。
定理 7.2.4 设 G 是具有 w(w≥1)个连通分支的平面图,各面的次数至少为 l(l ≥3)，
则 G 的边数 m 与顶点数 n 有如下关系,
证明,利用欧拉公式的推广形式 (定理 7.2.2)，与上一定理类似可证。
11
1
1111
2,( 1,2,).
,.,,
1,
2( ) 1
iii
ww
ii
ii
w
i
i
wwww
iii i i i
nmr i w
mmnn G G
Grrw
wnmr nmrnmrw
==
=
====
+= =
=?+
=?+=?+=?++?
∑∑
∑
∑∑∑∑
null
易知 由于 的每个分支有一个外部面 而 只有一个外部面故 的面数 于是整理即得结论,证毕.
1
2deg()
2.,2(2),
r
i
i
mRlr
rmn mlmn
=
=≥?
=+? ≥ +?
∑
由欧拉公式可知 将此式代入上式 得 整理便得结论。证毕。
3
10 (5 2) 9
32
≤?=
4
9(62)8
42
≤?=
(1).
2
l
mnw
l
≤
4
定理 7.2.5 设 G 是具有 m 条边的 n(n≥3) 阶简单平面图，则 m ≤ 3n?6 。
证明,设 G 有 w (w≥1) 个连通分支。若 G 为树或森林，则 m = n? w ≤ 3 n? 6 。
否则,G 中必有圈。因 G 是简单图，所以各圈的长度至少是 3，从而 G 中面的最小次数 l ≥ 3 。又因函数
在 l=3 时达到最大值 3，于是由定理 7.2.4,
证毕。
定理 7.2.6 具有 m 条边的 n(n ≥ 3) 阶简单连通的平面图 G 是极大平面图当且仅当 G 的每个面的次数均为 3。
证明,充分性,由定理 7.1.4 知,。因 G 是连通的，由欧拉公式可知,r =2+m–n。由此二式整理得,m =3n–6 。
假如 G 不是极大平面图，则 G 中一定存在不相邻的顶点 u 和 v，使得 G′
=G+uv 仍是简单平面图，而 G′ 的边数 m′ =m+1,n′ =n,结合 m =3n–6 得,m′ =
3n′ – 5> 3n′ – 6 。这与定理 7.2.5 矛盾。
必要性 设 G 是简单、连通的极大平面图，则 G 中无环边和重边，且由定理
7.1.6 可知,G 中无割边和割点。于是 G 中各面的次数至少为 3。以下用反证法证明 G 中各面的次数不会大于 3。从而使必要性得证。
事实上，假如 G 的某个面 R
i
的次数 deg(R
i
)=s ≥ 4，则 R
i
的边界上至少有 4
个顶点，设其中 4 个依次相邻的顶点为 v
1
,v
2
,v
3
,v
4
。若 v
1
与 v
3
在 G 中不相邻，
则在 R
i
内添加边 v
1
v
3
不破坏平面性，这与 G 是极大平面图矛盾。因而 v
1
与 v
3
在 G 中必定相邻。但因面 R
i
的存在，边 v
1
v
3
必在 R
i
的外边。类似地,v
2
与 v
4
在
G 中也必定相邻且边 v
2
v
4
必在 R
i
的外边。于是边 v
1
v
3
与边 v
2
v
4
必在 R
i
的外部相交。这与 G 是平面图矛盾。从而 G 中各面的次数不会大于 3。 证毕。
由该定理可知，下列平面图中，只有 (c)是极大平面图。
2
1
22
l
ll
=+
(1)3(2)36.
2
l
mnwnn
l
≤≤?=?
1
2deg()3
r
i
i
mRr
=
= =
∑
(a)
(c)
(b)
5
定理 7.2.7 设 G 是具有 m 条边的 n (n ≥ 3) 阶极大平面图，则 m=3n–6。
证明,由于极大平面图是连通图，由欧拉公式,r=2+m–n。 又因 G 是极大平面图，由定理 7.2.6 可知,G 的每个面的次数均为 3，故
由以上两式整理即得,m=3n–6 。证毕。
定理 7.2.8 设 G 是具有 m 条边的 n (n ≥ 3) 阶简单平面图，则 G 的最小度 δ ≤ 5。
证明,若 G 的阶数 n ≤ 6,则结论显然成立，下设 n ≥ 7 。假若 δ ≥ 6，则
因而 m ≥ 3n，这与定理 7.2.5 矛盾。证毕。
§ 7.3 平面图的判断
定义 7.3.1 设 e = uv 是图 G 的一条边。在 G 中删除 e，并添加新点 w，令 u 和 v
均与 w 相邻，这个过程称为在G中插入2度顶点w；反之，设 w 为 G 中一个 2
度顶点，设它的两个邻点为 u 和 v，删除 w 并添加新边 uv，这个过程称为在G
中消去2度顶点w。
定义 7.3.2 若两个图 G
1
和 G
2
同构，或者 G
1
和 G
2
经过反复插入或消去 2 度顶点后同构，则称 G
1
和 G
2
是 同胚的 。
例如，下列 (a)与 K
3
同胚,(b)与 K
4
同胚。
下列两个定理是平面图判定定理，证明从略。
定理 7.3.1 (库拉托夫斯基定理 1) 图 G 是平面图当且仅当 G 中既不含与 K
5
同胚的子图，也不含与 K
3,3
同胚的子图。
定理 7.3.2 (库拉托夫斯基定理 2) 图 G 是平面图当且仅当 G 中既没有可收缩到
K
5
的子图，也没有可收缩到 K
3,3
的子图。
1
2deg()3
r
i
i
mRr
=
==
∑
1
2()6.
n
i
i
mdvn
=
=≥
∑
(b) (a)
6
§ 7.4 平面图的对偶图
定义 7.4.1 设 G 是平面图的某个平面嵌入,G 的对偶图G* 构造如下,
在 G 的面 R
i
中放置 G* 的顶点 v
i
*。设 e 为 G 的任意一条边，若 e 在 G 的面 R
i
与 R
j
的公共边界上，做 G* 的边 e*与 e 相交，且 e* 关联 G* 的位于 R
i
和 R
j
中的顶点 v
i
*与 v
j
*，即 e*= v
i
*v
j
*,e* 不与其它任何边相交。若 e 为 G 中的割边且在面 R
i
的边界上，则 e*是以 R
i
中 G* 的顶点 v
i
*为端点的环，即 e* = v
i
*v
i
* 。
简单的说，平面图 G 的对偶图G* 就是以 G 的面作为顶点的图：用顶点代表 G 的各个面，两个面有 k 条公共边界，则相应的顶点间连 k 条边。若某个面中含有割边，则该面相应的点上连一条环边。
从定义不难看出 G 的对偶图 G* 有以下性质,
(1) G* 是平面图，而且是平面嵌入。
(2) G*是连通图。
(3) 若边 e 为 G 中的环边，则 G* 与 e 对应的边 e* 为割边；反之，若 e 为割边，则 G* 中与 e 对应的边 e* 为环边。
(4) 在多数情况下,G*为含重边的图。
(5) 同构的平面图（平面嵌入）的对偶图不一定是同构的。
例如,下列两图（实线边的图）是同构的，但它们的对偶图（虚线所示）
不同构，因为两个对偶图中环边所关联的顶点的度不相等,
平面图 G 与它的对偶图 G*的顶点数、边数和面数有如下关系。
定理 7.4.1 设 G*是连通平面图 G 的对偶图,n*,m*,r* 和 n,m,r 分别为 G*和 G
的顶点数、边数和面数,则
(1) n* = r; (2) m* = m; (3) r* = n ;
(4) 设 G*的顶点 v
i
* 位于 G 的面 R
i
中，则 d
G′
(v
i
* )=deg(R
i
)。
证明,由 G* 的构造可知,(1)和 (2)是显然的。
(3) 由于 G 与 G* 都连通，因而满足欧拉公式,
n－ m＋ r = 2,n*－ m*＋ r* = 2
7
由此及上述（ 1）、（ 2），便得
(4) 设 G 的面 R
i
的边界为 C
i
。设 C
i
中有 k
1
条割边 (k
1
≥0),k
2
条非割边，则 C
i
的长度为 k
2
+2k
1
,即 deg(R
i
) = k
2
+2k
1
。与 G 中这 k
1
条割边对应，在 G* 中 v
i
*处有 k
1
个环边，而 C
i
的 k
2
条非割边对应 G* 中从 v
i
* 处引出 k
2
条边，所以
定理 7.4.2 设 G
*
是具有 w 个连通分支的平面图 G 的对偶图,
则 (1) n* = r ;
(2) m* = m;
(3) r* = n－ w＋ 1;
(4) 设 v
i
* 位于 G 的面 R
i
中，则 d
G*
(v
i
* )=deg(R
i
)。
其中 n*,m*,r*,n,m,r 同前。
证明留作练习。
§ 7.5 平面图的面染色和四色猜想
一、平面图的面染色
定义 7.5.1 平面图的平面嵌入 G 的 面正常 k 染色 （ proper face k- colouring）是指
k 种颜色 1,2,,knull 在 G 的面集合 F(G)上的一种分配，使得有公共边的面所染颜色不同。用映射的观点看,G 的面正常 k 染色是一个映射
:(){1,2,,}cFG k→ null,
使得对每个 i ( ki,,2,1 null= ),)(
1
ic
内的面两两无公共边。
注,若令
1
() { ( ) ( ) },( 1,2,,)
i
F ci f FGcf i i k
==∈ ==null,则 G 的一个面正常 k
染色可看成是对面集合的一种划分
12
(,,,)
k
cFF F= null,其中每个 F
i
中的面彼此不相邻（无公共边）。
定义 7.5.2 若平面图的平面嵌入 G 存在一种面正常 k 染色，则称 G 是 面 k 色可染的 （ face k-colourable）。
定义 7.5.3 正整数 () min{GkGχ
= 面 k 色可染的 }称为 G 的 面色数 (face
chromatic number)。
例如,
4
()4Kχ
= 。
22.rmnmrn
=+? =+?=
*
*
21
() 2 deg().
ii
G
dv k k R=+ =
8
定理 7.5.1 设 G
是 G 的对偶图，则 (G) (G )χχ
= 。
证明,由定义立即可知。
四色猜想,任何地图只需用 4 种颜色来染色，就可使得任何具有公共边界的两个区域染不同的颜色 。
四色猜想的图论表述,对任何平面图的平面嵌入 G,(G) 4χ
≤ 。
二、四色猜想的几种等价表述
定理 7.5.2 对任何平面图 G,(G) 4χ ≤ 当且仅当其色多项式 (,4) 0PG > 。
证明,由色数和色多项式的定义立即可知。
定理 7.5.3 下列三个命题等价,
（ 1） 每个平面图都是点 4 可染的；
（ 2） 每个平面图的平面嵌入是面 4 可染的；
（ 3） 每个简单 2 边连通 3 正则平面图是边 3 色可染的。
证明,（ 1）?（ 2）设 G 是某平面图的一个平面嵌入,G
是其对偶图。则 G
也是平面图。由（ 1）,G
是点 4 色可染的。这种点 4 染色对应有 G 的一个 4
色正常面染色。
（ 2）?（ 3）设 G 是简单 2 边连通 3 正则平面图,G
null
是其一个平面嵌入。由 (2),
G
null
有面正常 4 染色? 。用
012 3
c (0,0),c (0,1),c (1,0),c (1,1)====来表示四种颜色。构造 G
null
的一种边染色如下,
对于边 ()eEG∈
null
，若 e 是某两个面,f g 的公共边且,f g 在? 下的颜色分别为,
ij
cc，则给 e 染颜色 () (mod2)
ij
Ce c c=+,
其中 c
i
与 c
j
的加法是向量相加，对各分量分别模 2。由于 G（从而 G
null
）是 2 边连通的，故 G
null
中每条边 e 都必定是某两个面的公共边，即 G
null
的每条边都被染色，并且这种染色只用到颜色 c
1
,c
2
,c
3
[因 c
0
,c
1
,c
2
,c
3
中不同的向量两两作加法 (模 2)只能得到 c
1
,c
2
,c
3
]。此外，由于 G
null
是 3 正则的，故每个顶点 u 关联
3 条边，设这 3 条边所夹的三个面的色为 c
i
,c
j
,c
k
（互不相同），则按边的染色规则，这 3 条边应分别染上色 c
i
+ c
j
,c
j
+ c
k
,c
k
+c
i
，这是三种不同的色。可见相邻的三边必染不同的色。因此 C 是 G
null
的一种正常的边 3 染色。
（ 3）?（ 1）假设（ 3）成立。下面用反证法证明（ 1）。
9
若存在一个平面图 G 不能用 4 种色正常染色，则其色数至少为 5。设 G
null
是
G 的一个平面嵌入，则存在一个三角剖分图 H，使得 G
null
是 H 的生成子图（留作习题）,H 的对偶图 H
是 2 边连通 3 正则的简单图（留作习题）。由（ 3），
H
是边 3 色可染的。设
123
(,,)cEEE= 是 H
的一个边正常 3 染色。对于 ij≠,
设 [],
ij i j
HHEE
=∪（只有
12 13 23
H,H,H三种）。因 H
中每个顶点都是 3 度的，故染色 c 的每种颜色都在 H
的每个顶点处出现，因而
ij
H
的每个顶点都是 2
度的，这样的图是边不相交的圈的并。
容易证明此时
ij
H
是面 2 色可染的。令
112 213
(){,} (){,}FH FH? αβ? γδ
→→：；,
分别是
12
H
和
13
H
的正常面 2 染色。于是 H
的每个面是
12
H
的某个面与
13
H
的某个面的交集的一部分。所以在
12
和下，面 f 获得两种颜色 x 和 y,记为 (x,y),
其中 xyα βγδ==或，或。定义四种新的颜色 (,),(,),(,),(,)α γαδβγβδ。易见
H
的每个面被这四种颜色之一所染。由于
12 13
HH H
= ∪,而且 H
的相邻两个面得到的颜色对不会相同，所以得到了 H
的一个面正常 4 染色。因 G
null
是 H 的生成子图，故 5(G)(G)(H) (H)4χχχχ
==≤= ≤
null
，这是不可能的。
这两个定理给出了四色猜想的四种等价表述,
(1) 面染色表述：对任何平面图的平面嵌入 G,(G) 4χ
≤ 。
(2) 点染色表述：对任何平面图 G,(G) 4χ ≤ 。
(3) 边染色表述：每个简单 2 边连通 3 正则平面图是边 3 色可染的。
(4) 色多项式表述：对任何平面图 G，色多项式 (,4) 0PG > 。
3
1
1
3
3 3
2 2
2
1
2
1
H
*
H
*
12
1
1
22
2
1
2
1
f
2
f
3
f
1
(,)α γ (,)β γ
(,)α δ
10
三、五色定理
定理 7.5.4 (五色定理,Heawood,1890) 对于任何平面图 G,(G) 5χ ≤ 。
证明,因为重边不影响点色数，故无妨设图 G 是平面简单图。对顶点数 ν 作数学归纳。
5ν ≤ 时，定理结论显然成立。
假设对 1nν ≤?的所有平面图，定理结论都成立。考虑 nν = 的情形。
由定理 7.2.8，存在
00
() () 5vVG dv∈≤，使得 。
（ 1）若
0
() 4dv ≤,考虑 G?v
0
。由归纳假设，
0
()5Gvχ? ≤ 。再给 v
0
染上与其邻点（不多于四个）相异的第五种色即可。
（ 2）若
0
()dv = 5,设 v
1
,v
2
,v
3
,v
4
,v
5
是 v
0
的邻点。将它们按逆时针顺序画在平面上，记 G
0
= G?v
0
。由归纳假设,G
0
可用五种色正常染色。设顶点 v
1
,v
2
,
v
3
,v
4
,v
5
在 G
0
中分别染以色 a,b,c,d,e。可以假定这五种色互不相同（如果 v
1
,
v
2
,v
3
,v
4
,v
5
中有染相同色的顶点，则可用第五种色给 v
0
染色）。用 G
ac
表示 G
0
中染 a 色和染 c 色的顶点导出的子图。
i）若 v
1
与 v
3
分别在 G
ac
的两个连通分支中，则在含有 v
1
的连通分支中将颜色 a,c 互换，这样便可给顶点 v
0
染色 a，从而得到 G 的一个点正常 5 染色。
ii）若 v
1
与 v
3
在 G
ac
的同一个连通分支中，则存在一个 (v
1
,v
3
)路 P，在 P 上顶点的色 a,c 交替出现。从图 G 中来看,v
0
v
1
+P+ v
3
v
0
是一个圈。由于 G 已嵌入平面，故 v
2
与 v
4
必分别处在该圈的内、外，因此在 G
0
中由 b,d 两色导出的子图 G
bd
中,v
2
与 v
4
分属于两个连通分支。（否则，在 G
bd
中有 (v
2
,v
4
)路 Pˊ,
它与路 P 相交于一个公共顶点 u，由于 u 在 Pˊ上，故应染有颜色 b 或 d,u 也在 P 上，又应染有颜色 a 或 c，这是不可能的）。无妨设 v
2
处在圈内，这时可将 v
2
所在的连通分支中 b 色与 d 色对换，再给 v
0
染上颜色 b，这样便可得到 G
的一个点正常 5 染色。证毕。
b
v
2
v
0
v
3
v
4
v
5
a
c
d
e
v
1
11
四、四色猜想简介
1852 年，英国学生 Francis Guthrie 在给英国地图染色时发现，只需要四种颜色就可以将相邻的区域区分开。于是向他的哥哥 Frederick Guthrie 提出如下猜想,任何地图只需用 4 种颜色来染色，就可使得任何具有公共边界的两个区域染不同的颜色 。
Frederick 转而请教他的老师、当时伦敦大学数学教授 A.De Morgan,A.De
Morgan 后来又写信将此猜想告诉给爱尔兰数学家 W,R,Hamilton。起初，这个问题并未引起人们的注意，但经过一段时间尝试之后，大家发现这个猜想并不容易被证明或被否定。 1878 年，当时伦敦数学会负责人 A,Cayley 向伦敦数学会成员正式公布了这个猜想。于是形成了著名的四色猜想。
z Kempe 给出的“证明”。
每个有界面都为 3 次面的平面图称为 构形 (configuration)。例如，下列四个平面图都是构形。
设 F 是由有限个构形组成的集合，若任何三角剖分平面图至少含有 F 中一个构形，则称 F 是 不可免完备集 （ unvoidable complete set）。
由定理 7.2.8，每个简单平面图的最小度≤ 5，从而任何三角剖分平面图的最小度也不超过 5，故上列四个构形组成的集合 F={O,P,Q,R}是一个不可免完备集。
如果有简单平面图 G 使得 (G) 5χ =,但对任何阶数小于 (G)ν 的平面图 H
均有 ()4Hχ ≤ 则称 G 是 极小图 (minimal graph)。根据 5 色定理可知，若四色猜想不真，则必存在极小图。
1879 年,Kempe 给出了四色猜想的第一个“证明”。他企图通过证明极小图不存在来证明四色猜想。“证明”使用反证法，思路如下。
若存在极小图 G，则易证 G 是一个三角剖分图，从而它必含有 F={O,P,Q,
R}中的构形。
若 G 含有构形 O 或 P，则由反证法假设,()4Gvχ? ≤ （ v 为构形的中心点）。设 π =(V
a
,V
b
,V
c
,V
d
)是图 G?v 的一个正常点 4 染色。则在染色 π 下,v 的
v
v
v v
P Q
O R
12
邻点集 N
G
(v)至多只需用到 3 种色，因而 4 色中可有一种色给点 v 染色，可见 π
也是图 G 的正常点 4 染色，这与 (G) 5χ = 矛盾。
若 G 含有构形 Q，则由反证法假设,()4Gvχ? ≤ (v 为构形 Q 的中心点 )。
设 π =(V
a
,V
b
,V
c
,V
d
)是图 G?v 的一个正常点 4 染色，并设 N
G
(v)={v
1
,v
2
,v
3
,v
4
}。
无妨假定
1234
,,,
abcd
vVvVvVvV∈∈∈∈，则 v
1
,v
4
在导出子图 G
ad
=G[V
a
∪ V
d
]中以及 v
2
,v
3
在导出子图 G
bc
=G[V
b
∪ V
c
]中不可能同时都是连通的（否则 G
ad
中
v
1
v
4
路与 G
bc
中 v
2
v
3
路会相交）。无妨设 v
1
和 v
4
在 G
ad
中不连通。这时交换 G
ad
中含 v
1
的连通分支中顶点的颜色，则 v
1
被染上色 d，而 v
2
,v
3
,v
4
的色不变。
因此可用色 a 来给点 v 染色，这样得到图 G 的一个正常点 4 染色，这又与
(G) 5χ = 矛盾。
Kempe 采用同样的方法“证明”了 G 也不可能含有构形 R，从而与 F 是不可免完备集矛盾。这样便“证明”了极小图不存在，四色猜想成立。
1890 年,P,J,Heawood 举出一个反例说明上述证明中 G 不含构形 R 的结论并非总能成立。从而否定了 Kempe 的证明。
z 寻找可约构形的不可免完备集。
设 S 是一个构形，若它不含在任何极小图中，则称 S 为 可约的 (reducible)。
Kempe 实际上证明了 O,P,Q 是可约的，但并没有证明 R 也是可约的。
尽管如此,Kempe 的证明提供了一条证明四色猜想的途径：寻找一个由可约构形组成的不可免完备集。
1904 年,P,Wernicke 找到一个新的不可免完备集（图 1）。
1913 年,G,D,Birkhoff 找出另一个不可免完备集（图 2）。
但他们都不能证明其中最后两个构形是可约的。
图 1
图 2
13
1913 年,G,D,Birkhoff 又发现了一个新的可约构形（图 3）。
此后，人们陆续发现了数千个可约构形。
1960 年,H,Heesch 试图用计算机在已发现的可约构形中找出不可免完备集，并提出一个判断给定的构形集合是否为不可免完备集的算法。
1961 年,Y,Shimamoto 宣布找到了一个由可约构形组成的不可免完备集。
但 Whitney 和 Tutte 在 1972 年发现 Shimamoto 在利用计算机判断时误算了一个构形的可约性。同时，他们提出了构形可约性分类理论。
1976 年,Apple 和 Haken 与 Koch 合作改进了 Heesch 的算法，并研究了可约构形的范围，最后利用计算机花了 1260 个机时，找到了一个由 1936 个可约构形组成的不可约完备集，从而宣布证明了四色猜想。
z Tait 的“证明”
值得提出的是,P.G,Tait 在 1880 年断言：每个 3 正则 3 连通平面图都是
Hamilton 图。在这个假设下他给出了四色猜想的一个证明。 60 多年后，
W.T.Tutte 于 1946 年构造出一个 3正则 3 连通非 Hamilton 平面图，从而否定了
Tait 的证明。
有关四色问题的更多内容可参看 [1]与 [2]，有关平面图的进一步了解可参看文献 [3]。
[1] D.R,Woodall and R.J,Wilson,The Appel-Haken proof of the four-color theorem,
Selected Topics in Graph Theory (eds,L,W,Beineke,and R.J,Wilson),Academic
Press,London,(1978) 83-101,
[2] R.C,Read,Some applications of computers in graph theory,Selected Topics in
Graph Theory,(eds,L,W,Beineke,and R.J,Wilson),Academic Press,New York,
(1978) 417-444,
[3] T,Nishizeki,and N,Chiba,Planar graphs,Theory and Algorithms,North-
Holland,Amsterdam,1988,
图 3
14
第七章习题
1.证明,(1) K
5
– e 是平面图； (2) K
3,3
– e 是平面图,
2,证明：不存在这样的平面图,它有 5 个面，且任二面间均至少有一条公共边。
3,(1) 证明：若 G 是围长 的连通平面图，则 。
(2)利用 (1)的结论证明,Peterson 图是非平面图。
4,证明每个平面图都是点 6 色可染的。
5,每个面的次都是 3 的平面图称为三角剖分平面图。证明顶点数至少为 3 的每个简单平面图都是某个三角剖分平面图的生成子图,
6,设 G 是至少含 4 个顶点的三角剖分简单平面图。证明其对偶图 G
*
是简单 2 边连通 3 正则平面图。
7,证明,设 G 是无割边的连通平面图,(G) 2ν ≥ 。证明,G 的平面嵌入是面 2 色可染的当且仅当 G 是 Euler 图。
8,证明,每个 Hamilton 平面图的平面嵌入都是面 4 色可染的。
3k ≥
(2)
2
k
k
ν
ε
≤
