第 17章 平面图及图的着色离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 平面图的基本概念
– 欧拉公式
– 平面图的判断
– 平面图的对偶图
– 顶点着色及点色数
– 地图的着色与平面图的点着色
– 边着色及边色数本章所涉及到的图均指无向图。
17.1 平面图的基本概念
17.2 欧拉公式
17.3 平面图的判断
17.4 平面图的对偶图
17.5 图中顶点的着色
17.6 地图的着色与平面图的点着色
17.7 边着色
本章小结
习 题
作 业
17.1 平面图的基本概念一,关于平面图的一些基本概念
1,平面图的定义定义 17.1
G可嵌入曲面 S—— 如果图 G能以这样的方式画在曲面 S上
,即除顶点处外无边相交 。
G是可平面图或平面图 —— 若 G可嵌入平面 。
G的平面嵌入 —— 画出的无边相交的平面图 。
非平面图 —— 无平面嵌入的图 。
（ 2） 是 （ 1） 的平面嵌入,（ 4） 是 （ 3） 的平面嵌入 。
2,几点说明及一些简单结论
一般所谈平面图不一定是指平面嵌入,但讨论某些性质时,
一定是指平面嵌入 。
K5和 K3,3都不是平面图 。
定理 17.1 设 GG,若 G为平面图,则 G?也是平面图 。
定理 17.2 设 GG,若 G?为非平面图,则 G也是非平面图 。
推论 Kn(n?5)和 K3,n(n?3)都是非平面图 。
定理 17.3 若 G为平面图，则在 G中加平行边或环所得图还是平面图。
即平行边和环不影响图的平面性。
二,平面图的面与次数 （ 针对平面图的平面嵌入 ）
1,定义定义 17.2 设 G是平面图,
G的面 —— 由 G的边将 G所在的平面划分成的每一个区域 。
无限面 （ 外部面 ） —— 面积无限的面,记作 R0。
有限面 （ 内部面 ） —— 面积有限的面,记作 R1,R2,…,Rk。
面 Ri的边界 —— 包围面 Ri的所有边组成的回路组 。
面 Ri的次数 —— Ri边界的长度，记作 deg(Ri)。
2,几点说明
若平面图 G有 k个面,可笼统地用 R1,R2,…,Rk表示,不需要指出外部面 。
回路组是指：边界可能是初级回路 （ 圈 ）,可能是简单回路,也可能是复杂回路 。 特别地,还可能是非连通的回路之并 。
平面图有 4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。
R1
R2
R3R0
定理 17.4 平面图 G中所有面的次数之和等于边数 m的两倍，即本定理中所说平面图是指平面嵌入。
e∈ E(G)，
当 e为面 Ri和 Rj(i≠j)的公共边界上的边时，在计算 Ri和 Rj的次数时,e各提供 1。
当 e只在某一个面的边界上出现时，则在计算该面的次数时
,e提供 2。
于是每条边在计算总次数时，都提供 2，因而 deg(Ri)=2m。
1
de g( ) 2
r
i
i
R m r G
其 中 为 的 面 数证明三,极大平面图
1,定义定义 17.3 若在简单平面图 G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称 G为极大平面图 。
注意,若简单平面图 G中已无不相邻顶点,G显然是极大平面图,如 K1（ 平凡图 ）,K2,K3,K4都是极大平面图 。
2,极大平面图的主要性质定理 17.5 极大平面图是连通的 。
定理 17.6 n(n?3)阶极大平面图中不可能有割点和桥 。
定理 17.7 设 G为 n(n?3) )阶简单连通的平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。
本节只证明必要性，即设 G为 n(n?3) )阶简单连通的平面图,G
为极大平面图，则 G的每个面的次数均为 3。
由于 n?3,又 G必为简单平面图,可知,G每个面的次数均?3。
因为 G为平面图,又为极大平面图 。 可证 G不可能存在次数 >3
的面 。
证明思路假设存在面 Ri的次数 deg(Ri)=s≥4，
如图所示。
在 G中，若 v1与 v3不相邻，在 Ri内加边 (v1,v3)不破坏平面性，这与 G是极大平面图矛盾，因而 v1与 v3必相邻，由于 Ri的存在，
边 (v1,v3)必在 Ri外。
类似地,v2与 v4也必相邻，且边 (v2,v4)也必在 Ri外部，于是必产生 (v1,v3)与 (v2,v4)相交于 Ri的外部，这又矛盾于 G是平面图，
所以必有 s＝ 3,即 G中不存在次数大于或等于 4的面，所以 G的每个面为 3条边所围，也就是各面次数均为 3。
s
S-1
只有右边的图为极大平面图。
因为只有该图每个面的次数都为 3。
四,极小非平面图定义 17.4 若在非平面图 G中任意删除一条边,所得图 G?为平面图,则称 G为极小非平面图 。
由定义不难看出：
K5,K3,3都是极小非平面图 。
极小非平面图必为简单图 。
例如,以下各图均为极小非平面图 。
小节结束
17.2 欧拉公式一、欧拉公式相关定理
1,欧拉公式定理 17.8 对于任意的连通的平面图 G,有
n-m+r=2
其中,n,m,r分别为 G的顶点数、边数和面数。
证明对边数 m作归纳法。
(1) m＝ 0时，由于 G为连通图，所以 G只能是由一个孤立顶点组成的平凡图，即 n=1,m=0,r=1,结论显然成立。
(2) m＝ 1时，由于 G为连通图，所以 n=2,m=1,r=1,结论显然成立。
(3)设 m＝ k(k≥1)时成立，当 m＝ k+1时，对 G进行如下讨论。
若 G是树，则 G是非平凡的，因而 G中至少有两片树叶。
设 v为树叶，令 G'=G-v,则 G'仍然是连通图，且 G'的边数
m'=m-1=k,n'=n-1,r'=r。
由假设可知 n'-m'+r'=2,式中 n',m',r'分别为 G'的顶点数，
边数和面数。
于是 n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2
若 G不是树，则 G中含圈。
设边 e在 G中某个圈上，令 G'=G-e,则 G'仍连通且 m'=m-1=k
,n'=n,r'=r-1。
由假设有 n'-m'+r'=2。
于是 n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2
定理 17.9 对于具有 k(k≥2)个连通分支的平面图 G,有
n-m+r = k+1
其中 n,m,r分别为 G的顶点数，边数和面数。
证明设 G的连通分支分别为 G1,G2,…,Gk,并设 Gi的顶点数、
边数、面数分别为 ni,mi,ri,i=1,2,…,k。
由欧拉公式可知,ni-mi+ri = 2,i=1,2,…,k (17.1)
易知，
11
kk
ii
ii
m m n n
，
由于每个 Gi 有一个外部面，而 G只有一个外部面，所以 G的面数
1
1
k
i
i
r r k
于是,对 (17.1)的两边同时求和得
1 1 1 1
2 ( ) 1
k k k k
i i i i i i
i i i i
k n m r n m r n m r k
经整理得 n-m+r = k+1。
2,与欧拉公式有关的定理定理 17.10 设 G为连通的平面图,且每个面的次数至少为
l(l? 3),则 G的边数与顶点数有如下关系：
由定理 17.4（ 面的次数之和等于边数的 2倍 ） 及欧拉公式得
( 2 )2lmnl
证明
1
2 d e g ( ) ( 2 )r i
i
m R l r l m n
解得 ( 2 )
2
lmn
l
推论 K5,K3,3不是平面图。
证明
若 K5是平面图，由于 K5中无环和平行边，所以每个面的次数均大于或等于 l≥3,由定理 17.10可知边数 10应满足
10≤(3/(3-2))(5-2) = 9
这是个矛盾，所以 K5不是平面图。
若 K3,3是平面图，由于 K3,3中最短圈的长度为 l≥4,于是边数 9
应满足
9≤ (4/(4-2))(6-2) = 8
这又是矛盾的，所以 K3,3也不是平面图。
定理 17.11设 G是有 k(k≥2)个连通分支的平面图，各面的次数至少为 l(l≥3),则边数 m与顶点数 n应有如下关系：
( 1 )2lm n kl
定理 17.12设 G为 n(n?3)阶 m条边的简单平面图，则 m?3n?6。
设 G有 k(k?1)个连通分支，
若 G为树或森林，当 n?3时,m=n-k?3n?6为真。
若 G不是树也不是森林，则 G中必含圈，又因为 G是简单图
，所以，每个面至少由 l（ l?3） 条边围成，又在 l=3达到最大值，由定理 17.11可知证明
2( 1 ) ( 1 ) ( 1 ) 3 ( 2 ) 3 6
22
lm n k n k n n
ll
定理 17.13设 G为 n(n?3)阶 m条边的极大平面图，则 m=3n?6。
证明由于极大平面图是连通图，由欧拉公式得,
r=2+m-n (17.4)
又因为 G是极大平面图，由定理 17.7的必要性可知,G的每个面的次数均为 3，所以：
将 (17.4)代入 (17.5)，整理后得 m = 3n-6。
1
2 d e g ( ) 3 ( 1 7,5 )
r
i
i
m R r
二,一个意义重大的定理定理 17.14 设 G为简单平面图,则 G的最小度?(G)?5。
若阶数 n?6,结论显然成立。
若阶数 n?7时，用反证法。
假设?(G)?6,由握手定理可知：
证明
1
2 ( ) 6
n
i
i
m d v n
＝
因而 m?3n,这与定理 17.12矛盾。
所以，假设不成立，即 G的最小度?(G)?5。
本定理在图着色理论中占重要地位。说明定理 17.7 设 G为 n(n?3) )阶简单连通的平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。（仅证充分性）
由定理 17.4可知，
证明
1
2 ( ) 3 ( 17.6)
n
i
i
m d v r
＝ ＝
又因为 G是连通的，由欧拉公式可知
2 ( 1 7,7 )r m n
将 (17.7)代入 (17.6)，经过整理得 m=3n-6。 (17.8)
若 G不是极大平面图，则 G中一定存在不相邻得顶点 u,v,使得
G?=G?(u,v)还是简单平面图，而 G?的边数 m?=m+1,n?=n。
由 (17.8)可知,m3n?－ 6,这与定理 17.2矛盾。
所以,G为极大平面图。 小节结束一,为判断定理做准备
1,插入 2度顶点和消去 2度顶点定义 17.5
设 e=(u,v)为图 G的一条边,在 G中删除 e,增加新的顶点 w，
使 u,v均与 w相邻,称为在 G中 插入 2度顶点 w。
设 w为 G中一个 2度顶点,w与 u,v相邻,删除 w,增加新边
(u,v),称为在 G中 消去 2度顶点 w。
17.3 平面图的判断
2,图之间的同胚定义 17.6 若两个图 G1与 G2同构,或通过反复插入或消去 2
度顶点后是同构的,则称 G1与 G2是 同胚 的 。
上面两个图分别与 K3,3,K5同胚 。
二,两个判断定理定理 17.15(库拉图斯基定理 1) 图 G是平面图当且仅当 G中既不含与 K5同胚子图,也不含与 K3,3同胚子图 。
定理 17.16(库拉图斯基定理 2) 图 G是平面图当且仅当 G中既没有可以收缩到 K5的子图,也没有可以收缩到 K3,3的子图 。
例 17.1 证明彼得松图不是平面图。
将彼得松图顶点标顺序,见图 (1)所示 。
证明还可以这样证明：
用 G表示彼得松图,令 G'=G-{(j,g),(c,d)}
G‘如图 (3)所示,易知它与 K3,3同胚,
在图中将边 (a,f),(b,g),(c,h),(d,i),(e,j)收缩，
所得图为图 (2)所示，它是 K5，
由定理 17.16可知，彼得松图不是平面图。
由定理 17.15可知,G为非平面图。
例 17.2 对 K5插入 2度顶点，或在 K5外放置一个顶点使其与 K5上的若干顶点相邻，共可产生多少个 6阶简单连通非同构的非平面图？
用插入 2度顶点的方法只能产生一个非平面图,如图 (1)所示 。
解答在 K5外放置一个顶点,使其与
K5上的 1个到 5个顶点相邻,得 5
个图,如图 (2)到 (6)所示 。
它与 K5同胚,所以是非平面图 。
它们都含 K5为子图,由库拉图斯基定理可知,它们都是非平面图,并且也满足其它要求 。
例 17.3 由 K3,3加若干条边能生成多少个 6阶连通的简单的非同构的非平面图？
对 K3,3加 1～ 6条边所得图都含 K3,3为子图，由库拉图斯基定理可知，它们都是非平面图。
在加 2条、加 3条、加 4条边时又各产生两个非同构的非平面图，
连同 K3,3本身共有 10个满足要求的非平面图。其中，绿线边表示后加的新边。
解答小节结束
17.4 平面图的对偶图一,对偶图的定义定义 17.7 设 G是某平面图的某个平面嵌入,构造 G的对偶图
G*如下：
在 G的面 Ri中放置 G*的顶点 vi*。
设 e为 G的任意一条边,
若 e在 G的面 Ri与 Rj的公共边界上,做 G*的边 e*与 e相交,
且 e*关联 G*的位于 Ri与 Rj中的顶点 vi*与 vj*,即 e*=(vi*,vj*)
,e*不与其它任何边相交 。
若 e为 G中的桥且在面 Ri的边界上，则 e*是以 Ri中 G*的顶点
vi*为端点的环，即 e*=(vi*,vi*)。
实线边图为平面图，虚线边图为其对偶图。
从定义不难看出 G的对偶图 G*有以下性质：
G*是平面图,而且是平面嵌入 。
G*是连通图 。
若边 e为 G中的环,则 G*与 e对应的边 e*为桥,若 e为桥,
则 G*中与 e对应的边 e*为环 。
在多数情况下,G*为多重图 （ 含平行边的图 ） 。
同构的平面图 （ 平面嵌入 ） 的对偶图不一定是同构的 。
二,平面图与对偶图的阶数,边数与面数之间的关系 。
定理 17.17 设 G*是连通平面图 G的对偶图,n*,m*,r*和 n
,m,r分别为 G*和 G的顶点数,边数和面数,则
（ 1） n*= r
（ 2） m*=m
（ 3） r*=n
（ 4） 设 G*的顶点 v*i位于 G的面 Ri中,则 dG*(vi*)=deg(Ri)
(1),(2)由 G*的构造可知是显然的。
(3)由于 G与 G*都连通，因而满足欧拉公式,
n-m+r = 2
n*-m*+r* = 2
由 (1),(2))可知,r* = 2+m*-n* = 2+m-r = n
(4)设 G的面 Ri的边界为 Ci,设 Ci中有 k1(k1≥0)条桥,k2个非桥边
，于是
Ci的长度为 k2+2k1,即 deg(Ri)＝ k2+2k1，
k1条桥对应 vi*处有 k1个环,k2条非桥边对应从 vi*处引出 k2条边，
所以 dG*(vi*)＝ k2+2k1＝ deg(Ri)。
证明定理 17.18 设 G*是具有 k（ k?2） 个连通分支的平面图 G的对偶图,n*,m*,r*,n,m,r分别为 G*和 G的顶点数,边数和面数,
（ 1） n*= r
（ 2） m*=m
（ 3） r*=n?k+1
（ 4） 设 G*的顶点 v*i位于 G的面 Ri中,则 dG*(v*i)=deg(Ri)
三,自对偶图定义 17.8 设 G*是平面图 G的对偶图,若 G*?G,则称 G为自对偶图 。
在 n?1(n?4)边形 Cn?1内放置 1个顶点,使这个顶点与 Cn?1上的所有的顶点均相邻,所得 n阶简单图称为 n阶轮图 。 记为 Wn。
n为奇数的轮图称为 奇阶轮图 。
n为偶数的轮图称为 偶阶轮图 。
轮图都是自对偶图 。
小节结束
17.5 图中顶点的着色规定,点着色都是对无环无向图进行的 。
一,关于顶点着色的基本概念定义 17.9
（ 1） 图 G的一种着色 —— 对无环图 G的每个顶点涂上一种颜色,使相邻顶点涂不同的颜色 。
（ 2） 对 G进行 k着色 （ G是 k-可着色的 ） —— 能用 k种颜色给 G
的顶点着色 。
（ 3） G的色数?(G)=k—— G是 k-可着色的，但不是 (k?1)-可着色的。
二,关于顶点着色的几个简单结果定理 17.19?(G)=1当且仅当 G为零图 。
定理 17.20?(Kn)=n。
定理 17.21奇圈或奇阶轮图的色数均为 3,偶阶轮图的色数为 4。
定理 17.22 设 G中至少含有一条边，则?(G)=2当且仅当 G为二部图。
三、色数的上界定理 17.23 对于任意无向图 G,均有?(G)(G)+1。
n=1时,结论成立 。
设 n=k(k≥1)时结论成立,则当 n=k+1时,
设 v为 G中任一个顶点,令 G'=G-v,则 G'的阶数为 k,由假设可知?(G')(G')+1≤Δ(G)+1。
当将 G'还原成 G时,由于 v至多与 G'中 Δ(G)个顶点相邻,而在
G'的点着色中,Δ(G)个顶点至多用了 Δ(G)种颜色,于是在
Δ(G)+1种颜色中至少存在一种颜色给 v涂色,使 v与相邻顶点涂不同颜色 。
证明 提示：对 G的阶数 n作归纳法。
例 17.4 求下面各图的色数。
定理 17.24 (布鲁克斯定理 ) 若连通无向图 G不是 Kn(n?3),也不是奇数阶的圈，则?(G)(G)。
因为 (1)为二部图，由定理 17.22可知,?(G) =2。
(2)为 6阶轮图 W6,由定理 17.21可知,?(G) =4。
由定理 17.24可知,?(G)≤4,又因为 (3)中有奇圈，于是?(G)
≥3,因而?(G)为 3或 4，用 3种颜色不可能给 G4着色，于是只能是?(G) =4。
解答小节结束
17.6 地图的着色与平面图的点着色一,地图与面着色
1,地图与国家定义 17.10
（ 1） 地图 —— 连通无桥平面图的平面嵌入与所有的面 。
（ 2） 国家 —— 地图的面 。
（ 3） 两个国家相邻 —— 两个国家的边界至少有一条公共边 。
有 5个国家，
1与 2相邻,1与 4相邻，
2,3,4均与 5相邻。
5 4 1 2 3
2,地图的面着色定义 17.11
（ 1） 地图 G的一种面着色 —— 对地图 G的每个国家涂上一种颜色,使相邻国家涂不同的颜色 。
（ 2） G是 k-面可着色的 —— 能用 k种颜色给 G的面着色,就称对 G的面进行了 k着色 。
（ 3） G的面色数?*(G)=k—— G是 k-面可着色的,但不是 (k-1)-
面可着色的,即最少用 k种颜色给 G的面着色 。
研究地图的着色可以转化成对它的对偶图的点着色 。说明二,地图的面着色转化成对偶图的点着色定理 17.25 地图 G是 k-面可着色的当且仅当它的对偶图 G*是 k-
点可着色的 。
三,五色定理定理 17.26 任何平面图都是 5-可着色的 。
四色猜想问题,提出来已经近 150年了,但时至今日还没有得到彻底解决 。
小节结束
17.7 边着色本节讨论的图是无环的无向图 。
一,对图 G进行边着色定义 17.12
（ 1） 对图 G边的一种着色 —— 对图 G的每条边涂上一种颜色,
使相邻的边涂不同的颜色 。
（ 2） G是 k-边可着色的 —— 能用 k种颜色给 G的边着色 。
（ 3） G的边色数(G)=k—— 若 G是 k-边可着色的,但不是
(k-1)-边可着色的,即 最少用 k种颜色给 G的边着色 。
二、关于边着色的一些定理定理 17.27 G为简单平面图，则?(G)(G)(G)+1。
该定理是维津定理。
定理说明，对简单图来说，它的边色数 χ‘只能取它的
(G),或者是它的?(G) +1。
究竟哪些图的(G)是?(G),哪些是?(G) +1,至今还是一个没有解决的问题。
定理 17.28
设 G为长度大于或等于 2的偶圈，则 χ'(G)=Δ(G)=2.
设 G为长度大于或等于 3的奇圈，则 χ'(G)=Δ(G)+1=3,
n=4时,由维津定理可知,结论正确 。
n=5时,由维津定理可知,结论正确 。
n≥6时,Δ(Wn)=n-1≥5,Wn中间顶点关联的 n-1条边必须用 n-1
种颜色着色 。
而外圈 Cn-1上的任何边都准确的与其余的 4条边相邻,于是总可以找到 n-1种色中的一种为它涂色,所以 χ'(Wn)≤n-1。
又由维津定理可知,χ'(Wn)≥n-1,所以 χ'(Wn)=n-1。
定理 17.29(Wn) =?(Wn) = n?1,其中 n?4。
定理 17.30 二部图的边色数等于最大度 。
证明定理 17.31
当 n(n?1)为奇数时,(Kn)=n； 当 n为偶数时,(Kn)=n?1。
例 17.5 证明 χ'(W4)=Δ(W4)=3,χ'(W5)=Δ(W5)=4。
由维津定理可知结论是正确的。
解答例 17.6 求下面所示各图的边色数。
小节结束
(1)中无奇长回路，所以它为二部图，由定理 17.30可知
χ'=Δ=4。
由维津定理可知,(2)中 χ'≥Δ=4,又存在 4种颜色的边着色，
所以 χ'≤4,因而 χ'=4。
解答本章主 要内容
平面图及平面嵌入 。
平面图的面与次数 。
极大平面图及性质 。
极小非平面图 。
欧拉公式及其推广 。
平面图的边数 m与顶点数 n的关系 。
简单平面图 G中,δ(G)≤5。
库拉图斯基的两个定理 。
平面图的对偶图 。
本章主 要内容
顶点的着色与点色数 。
关于点色数的一些定理 。
地图及其面着色,面色数 。
平面图的五色定理 。
边着色及边色数 。
关于边着色的一些定理 。
本章学习要求
深刻理解本部分的基本概念：平面图,平面嵌入,平面图的面,次数,极大平面图,极小非平面图,平面图的对偶图,
自对偶图等 。
熟练掌握极大平面的性质,特别是充分必要条件 。
熟练掌握并会应用欧拉公式及其推广形式 。
掌握由欧拉公式及其推广形式所证明的平面的性质 。
会用库拉图斯基定理证明某些图不是平面图 。
掌握平面图与其对偶图某些关系的定理 。
深刻理解点着色,边着色,点色数,边色数的概念 。
理解并记住地图面着色与它的对偶图点着色的关系的定理 。
会应用点色数及边色数解决一些简单的实际问题 。
小节结束
1,设 G 是连通的简单的平面图，面数 r < 12,? ( G )? 3,
（ 1 ）证明 G 中存在次数? 4 的面
（ 2 ）举例说明当 r = 12 时，（ 1 ）中结论不真,
解本题可用的定理有欧拉公式、握手定理、各面次之和与边数的关系等,使用反证法证明,设 G 的阶数、边数、面数分别为 n,m,r,
（ 1 ）否则，由欧拉公式得
2 m > 5 r = 5 ( 2+ m? n ) ①
由于? ( G )? 3 及握手定理又有
2 m? 3 n ②
由 ① 与 ② 得 m? 3 0 ③
又有
r = 2+ m? n < 1 2 ④
由 ④ 及 ② 又可得
m < 30 ⑤
③,⑤ 是矛盾的,
（ 2 ）正十二面体是一个反例,
解只需证明 G 和 G 中至少有一个是非平面图,采用反证法,否则 G 与
G 都是平面图，下面来推出矛盾,
G 与 G 的边数 m,m? 应满足
2
)1(
'
nn
mm （ K
n
的边数） ①
由鸽巢原理知 m 或 m?,不妨设 m,
4
)1(?
nn
m ②
又由定理 1 7,12 知 m? 3 n? 6 ③
由 ② 与 ③ 得 n
2
13 n + 24? 0 ④
由 ④ 解得 2? n? 10 ⑤
⑤ 与 n? 11 矛盾,
其实，当 n = 9,1 0 时，命题结论已真,
2,设 G 是阶数 n? 11 的无向平面图，证明 G 和 G 不可能全是平面图,
证
3,证明图 14 所示图为非平面图图 14
用库拉图斯基定理证明方法一,图 15 所示图为图 14 所示图的子图，它是 K
3,3
（请找出互补顶点子集），由库拉图斯基定理得证命题,
图 15
证方法二,
图 16 所示图为图 14 的子图（删除边 ( a,f ) ），收缩图 16 中 的
( a,e ) 和 ( f,g ) 所得图为 K
5
,由库拉图斯基定理得证命题,
图 16
证证明中用 到 n? 3 的极大平面图的性质，以及平面图与对偶图的关系，对偶图的连通性等,
（ 1 ）证 G * 是 2 - 边连通的,
由 G * 的连通性可知,? ( G *)? 1,又因为 G 为极大平面图，故 G 为简单图，所以 G * 中无桥（因为 G 中无环），
所以,? ( G *)? 2,故 G * 为 2 - 边连通的,
（ 2 ）证 G * 是 3 - 正则图,
易知 G * 为简单图，且每个顶点的度数均为 3 （由定理
17.7 决定），故 G * 为 3 - 正则图,
4,设 G 为 n （ n? 3 ）阶极大平面图，证明 G 的对偶图 G * 是 2 -
边连通的 3 - 正则图,
证
5,求图 17 所示图的点色数?,边色数,以及面色数? *,
图 17
（ 1 ）因为 G 中含奇圈，所以 3,由布鲁克斯定理知 = 4,
又容易证明不能用 3 种颜色涂色：由于 a,b,c 彼此相邻，
因而至少用 3 种颜色涂色，设用颜色?,?,? 分别给 a,b,
c 涂色,此时最省还用这三种颜色给 d,e,f 涂色，而且
d,e,f 也只能用颜色?,? 和?,这样 g 只能用另一种颜色，
比如? 涂色，所以? = 4,
解
（ 2 ）由维津（ V i z i ng ）定理可知 =4 或 5,但可用 4 种颜色给边涂色，见图 18 所示,
图 18
（ 3 ）易知图 17 的对偶图为图 19 所示，容易证明它的点色数为 4,所以图
17 的面色数? *= 4,见图 20 所示,
图 20图 19
用维津定理及握手定理即可证,
由维津定理知 3 =? ( G ) ( G ) ( G ) + 1 = 4,下面只需证可用 3 种颜色给 G 的边着色,设 C 为 G 中的哈密顿回路，则 C 为偶圈（ 3 n =2 m ），所以用两种颜色可给 C 的边着色,G 中不在 C 上的边彼此不邻（为什么？），因而用第 3 种颜色给它们着色即可,
6,设 G 为 3 - 正则的哈密顿图，证明( G ) = 3,
证
7,某校计算机系三年级学生在本学期共选 6 门选修课 C
i
,
i = 1,2,…,6,
设 S ( C
i
) 为选 C
i
课的学生集,已知
S ( C
i
)? S ( C
6
),i = 1,2,…,5,
S ( C
i
)? S ( C
i +1
),i = 1,2,3,4,
S ( C
5
)? S ( C
1
),
问这 6 门课至少几天能考完？
由已知条件做无向图 G =< V,E >,
其中 V ={ C
1
,C
2
,…,C
6
},
E = {( Ci,Cj ) | S ( C
i
)? S ( C
j
) },
见图 21 所示 W
6
,
给 G 一种着色（点着色）,
C
i
与 C
j
着同色
C
i
与 C
j
不相邻
没有学生既学 C
i
又学 C
j
C
i
与 C
j
可同时考,
图 21
于是最少的考试时间为
( G ) = 4 （见定理 17.2 1 ）,
解小节结束作业习题十七,
1,3,15,24,26,29
结束
本章的主要内容
– 平面图的基本概念
– 欧拉公式
– 平面图的判断
– 平面图的对偶图
– 顶点着色及点色数
– 地图的着色与平面图的点着色
– 边着色及边色数本章所涉及到的图均指无向图。
17.1 平面图的基本概念
17.2 欧拉公式
17.3 平面图的判断
17.4 平面图的对偶图
17.5 图中顶点的着色
17.6 地图的着色与平面图的点着色
17.7 边着色
本章小结
习 题
作 业
17.1 平面图的基本概念一,关于平面图的一些基本概念
1,平面图的定义定义 17.1
G可嵌入曲面 S—— 如果图 G能以这样的方式画在曲面 S上
,即除顶点处外无边相交 。
G是可平面图或平面图 —— 若 G可嵌入平面 。
G的平面嵌入 —— 画出的无边相交的平面图 。
非平面图 —— 无平面嵌入的图 。
（ 2） 是 （ 1） 的平面嵌入,（ 4） 是 （ 3） 的平面嵌入 。
2,几点说明及一些简单结论
一般所谈平面图不一定是指平面嵌入,但讨论某些性质时,
一定是指平面嵌入 。
K5和 K3,3都不是平面图 。
定理 17.1 设 GG,若 G为平面图,则 G?也是平面图 。
定理 17.2 设 GG,若 G?为非平面图,则 G也是非平面图 。
推论 Kn(n?5)和 K3,n(n?3)都是非平面图 。
定理 17.3 若 G为平面图，则在 G中加平行边或环所得图还是平面图。
即平行边和环不影响图的平面性。
二,平面图的面与次数 （ 针对平面图的平面嵌入 ）
1,定义定义 17.2 设 G是平面图,
G的面 —— 由 G的边将 G所在的平面划分成的每一个区域 。
无限面 （ 外部面 ） —— 面积无限的面,记作 R0。
有限面 （ 内部面 ） —— 面积有限的面,记作 R1,R2,…,Rk。
面 Ri的边界 —— 包围面 Ri的所有边组成的回路组 。
面 Ri的次数 —— Ri边界的长度，记作 deg(Ri)。
2,几点说明
若平面图 G有 k个面,可笼统地用 R1,R2,…,Rk表示,不需要指出外部面 。
回路组是指：边界可能是初级回路 （ 圈 ）,可能是简单回路,也可能是复杂回路 。 特别地,还可能是非连通的回路之并 。
平面图有 4个面,deg(R1)=1,deg(R2)=3,deg(R3)=2,deg(R0)=8。
R1
R2
R3R0
定理 17.4 平面图 G中所有面的次数之和等于边数 m的两倍，即本定理中所说平面图是指平面嵌入。
e∈ E(G)，
当 e为面 Ri和 Rj(i≠j)的公共边界上的边时，在计算 Ri和 Rj的次数时,e各提供 1。
当 e只在某一个面的边界上出现时，则在计算该面的次数时
,e提供 2。
于是每条边在计算总次数时，都提供 2，因而 deg(Ri)=2m。
1
de g( ) 2
r
i
i
R m r G
其 中 为 的 面 数证明三,极大平面图
1,定义定义 17.3 若在简单平面图 G中的任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称 G为极大平面图 。
注意,若简单平面图 G中已无不相邻顶点,G显然是极大平面图,如 K1（ 平凡图 ）,K2,K3,K4都是极大平面图 。
2,极大平面图的主要性质定理 17.5 极大平面图是连通的 。
定理 17.6 n(n?3)阶极大平面图中不可能有割点和桥 。
定理 17.7 设 G为 n(n?3) )阶简单连通的平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。
本节只证明必要性，即设 G为 n(n?3) )阶简单连通的平面图,G
为极大平面图，则 G的每个面的次数均为 3。
由于 n?3,又 G必为简单平面图,可知,G每个面的次数均?3。
因为 G为平面图,又为极大平面图 。 可证 G不可能存在次数 >3
的面 。
证明思路假设存在面 Ri的次数 deg(Ri)=s≥4，
如图所示。
在 G中，若 v1与 v3不相邻，在 Ri内加边 (v1,v3)不破坏平面性，这与 G是极大平面图矛盾，因而 v1与 v3必相邻，由于 Ri的存在，
边 (v1,v3)必在 Ri外。
类似地,v2与 v4也必相邻，且边 (v2,v4)也必在 Ri外部，于是必产生 (v1,v3)与 (v2,v4)相交于 Ri的外部，这又矛盾于 G是平面图，
所以必有 s＝ 3,即 G中不存在次数大于或等于 4的面，所以 G的每个面为 3条边所围，也就是各面次数均为 3。
s
S-1
只有右边的图为极大平面图。
因为只有该图每个面的次数都为 3。
四,极小非平面图定义 17.4 若在非平面图 G中任意删除一条边,所得图 G?为平面图,则称 G为极小非平面图 。
由定义不难看出：
K5,K3,3都是极小非平面图 。
极小非平面图必为简单图 。
例如,以下各图均为极小非平面图 。
小节结束
17.2 欧拉公式一、欧拉公式相关定理
1,欧拉公式定理 17.8 对于任意的连通的平面图 G,有
n-m+r=2
其中,n,m,r分别为 G的顶点数、边数和面数。
证明对边数 m作归纳法。
(1) m＝ 0时，由于 G为连通图，所以 G只能是由一个孤立顶点组成的平凡图，即 n=1,m=0,r=1,结论显然成立。
(2) m＝ 1时，由于 G为连通图，所以 n=2,m=1,r=1,结论显然成立。
(3)设 m＝ k(k≥1)时成立，当 m＝ k+1时，对 G进行如下讨论。
若 G是树，则 G是非平凡的，因而 G中至少有两片树叶。
设 v为树叶，令 G'=G-v,则 G'仍然是连通图，且 G'的边数
m'=m-1=k,n'=n-1,r'=r。
由假设可知 n'-m'+r'=2,式中 n',m',r'分别为 G'的顶点数，
边数和面数。
于是 n-m+r=(n'+1)-(m'+1)+r'=n'-m'+r'=2
若 G不是树，则 G中含圈。
设边 e在 G中某个圈上，令 G'=G-e,则 G'仍连通且 m'=m-1=k
,n'=n,r'=r-1。
由假设有 n'-m'+r'=2。
于是 n-m+r=n'-(m'+1)-(r'+1)=n'-m'+r'=2
定理 17.9 对于具有 k(k≥2)个连通分支的平面图 G,有
n-m+r = k+1
其中 n,m,r分别为 G的顶点数，边数和面数。
证明设 G的连通分支分别为 G1,G2,…,Gk,并设 Gi的顶点数、
边数、面数分别为 ni,mi,ri,i=1,2,…,k。
由欧拉公式可知,ni-mi+ri = 2,i=1,2,…,k (17.1)
易知，
11
kk
ii
ii
m m n n
，
由于每个 Gi 有一个外部面，而 G只有一个外部面，所以 G的面数
1
1
k
i
i
r r k
于是,对 (17.1)的两边同时求和得
1 1 1 1
2 ( ) 1
k k k k
i i i i i i
i i i i
k n m r n m r n m r k
经整理得 n-m+r = k+1。
2,与欧拉公式有关的定理定理 17.10 设 G为连通的平面图,且每个面的次数至少为
l(l? 3),则 G的边数与顶点数有如下关系：
由定理 17.4（ 面的次数之和等于边数的 2倍 ） 及欧拉公式得
( 2 )2lmnl
证明
1
2 d e g ( ) ( 2 )r i
i
m R l r l m n
解得 ( 2 )
2
lmn
l
推论 K5,K3,3不是平面图。
证明
若 K5是平面图，由于 K5中无环和平行边，所以每个面的次数均大于或等于 l≥3,由定理 17.10可知边数 10应满足
10≤(3/(3-2))(5-2) = 9
这是个矛盾，所以 K5不是平面图。
若 K3,3是平面图，由于 K3,3中最短圈的长度为 l≥4,于是边数 9
应满足
9≤ (4/(4-2))(6-2) = 8
这又是矛盾的，所以 K3,3也不是平面图。
定理 17.11设 G是有 k(k≥2)个连通分支的平面图，各面的次数至少为 l(l≥3),则边数 m与顶点数 n应有如下关系：
( 1 )2lm n kl
定理 17.12设 G为 n(n?3)阶 m条边的简单平面图，则 m?3n?6。
设 G有 k(k?1)个连通分支，
若 G为树或森林，当 n?3时,m=n-k?3n?6为真。
若 G不是树也不是森林，则 G中必含圈，又因为 G是简单图
，所以，每个面至少由 l（ l?3） 条边围成，又在 l=3达到最大值，由定理 17.11可知证明
2( 1 ) ( 1 ) ( 1 ) 3 ( 2 ) 3 6
22
lm n k n k n n
ll
定理 17.13设 G为 n(n?3)阶 m条边的极大平面图，则 m=3n?6。
证明由于极大平面图是连通图，由欧拉公式得,
r=2+m-n (17.4)
又因为 G是极大平面图，由定理 17.7的必要性可知,G的每个面的次数均为 3，所以：
将 (17.4)代入 (17.5)，整理后得 m = 3n-6。
1
2 d e g ( ) 3 ( 1 7,5 )
r
i
i
m R r
二,一个意义重大的定理定理 17.14 设 G为简单平面图,则 G的最小度?(G)?5。
若阶数 n?6,结论显然成立。
若阶数 n?7时，用反证法。
假设?(G)?6,由握手定理可知：
证明
1
2 ( ) 6
n
i
i
m d v n
＝
因而 m?3n,这与定理 17.12矛盾。
所以，假设不成立，即 G的最小度?(G)?5。
本定理在图着色理论中占重要地位。说明定理 17.7 设 G为 n(n?3) )阶简单连通的平面图,G为极大平面图当且仅当 G的每个面的次数均为 3。（仅证充分性）
由定理 17.4可知，
证明
1
2 ( ) 3 ( 17.6)
n
i
i
m d v r
＝ ＝
又因为 G是连通的，由欧拉公式可知
2 ( 1 7,7 )r m n
将 (17.7)代入 (17.6)，经过整理得 m=3n-6。 (17.8)
若 G不是极大平面图，则 G中一定存在不相邻得顶点 u,v,使得
G?=G?(u,v)还是简单平面图，而 G?的边数 m?=m+1,n?=n。
由 (17.8)可知,m3n?－ 6,这与定理 17.2矛盾。
所以,G为极大平面图。 小节结束一,为判断定理做准备
1,插入 2度顶点和消去 2度顶点定义 17.5
设 e=(u,v)为图 G的一条边,在 G中删除 e,增加新的顶点 w，
使 u,v均与 w相邻,称为在 G中 插入 2度顶点 w。
设 w为 G中一个 2度顶点,w与 u,v相邻,删除 w,增加新边
(u,v),称为在 G中 消去 2度顶点 w。
17.3 平面图的判断
2,图之间的同胚定义 17.6 若两个图 G1与 G2同构,或通过反复插入或消去 2
度顶点后是同构的,则称 G1与 G2是 同胚 的 。
上面两个图分别与 K3,3,K5同胚 。
二,两个判断定理定理 17.15(库拉图斯基定理 1) 图 G是平面图当且仅当 G中既不含与 K5同胚子图,也不含与 K3,3同胚子图 。
定理 17.16(库拉图斯基定理 2) 图 G是平面图当且仅当 G中既没有可以收缩到 K5的子图,也没有可以收缩到 K3,3的子图 。
例 17.1 证明彼得松图不是平面图。
将彼得松图顶点标顺序,见图 (1)所示 。
证明还可以这样证明：
用 G表示彼得松图,令 G'=G-{(j,g),(c,d)}
G‘如图 (3)所示,易知它与 K3,3同胚,
在图中将边 (a,f),(b,g),(c,h),(d,i),(e,j)收缩，
所得图为图 (2)所示，它是 K5，
由定理 17.16可知，彼得松图不是平面图。
由定理 17.15可知,G为非平面图。
例 17.2 对 K5插入 2度顶点，或在 K5外放置一个顶点使其与 K5上的若干顶点相邻，共可产生多少个 6阶简单连通非同构的非平面图？
用插入 2度顶点的方法只能产生一个非平面图,如图 (1)所示 。
解答在 K5外放置一个顶点,使其与
K5上的 1个到 5个顶点相邻,得 5
个图,如图 (2)到 (6)所示 。
它与 K5同胚,所以是非平面图 。
它们都含 K5为子图,由库拉图斯基定理可知,它们都是非平面图,并且也满足其它要求 。
例 17.3 由 K3,3加若干条边能生成多少个 6阶连通的简单的非同构的非平面图？
对 K3,3加 1～ 6条边所得图都含 K3,3为子图，由库拉图斯基定理可知，它们都是非平面图。
在加 2条、加 3条、加 4条边时又各产生两个非同构的非平面图，
连同 K3,3本身共有 10个满足要求的非平面图。其中，绿线边表示后加的新边。
解答小节结束
17.4 平面图的对偶图一,对偶图的定义定义 17.7 设 G是某平面图的某个平面嵌入,构造 G的对偶图
G*如下：
在 G的面 Ri中放置 G*的顶点 vi*。
设 e为 G的任意一条边,
若 e在 G的面 Ri与 Rj的公共边界上,做 G*的边 e*与 e相交,
且 e*关联 G*的位于 Ri与 Rj中的顶点 vi*与 vj*,即 e*=(vi*,vj*)
,e*不与其它任何边相交 。
若 e为 G中的桥且在面 Ri的边界上，则 e*是以 Ri中 G*的顶点
vi*为端点的环，即 e*=(vi*,vi*)。
实线边图为平面图，虚线边图为其对偶图。
从定义不难看出 G的对偶图 G*有以下性质：
G*是平面图,而且是平面嵌入 。
G*是连通图 。
若边 e为 G中的环,则 G*与 e对应的边 e*为桥,若 e为桥,
则 G*中与 e对应的边 e*为环 。
在多数情况下,G*为多重图 （ 含平行边的图 ） 。
同构的平面图 （ 平面嵌入 ） 的对偶图不一定是同构的 。
二,平面图与对偶图的阶数,边数与面数之间的关系 。
定理 17.17 设 G*是连通平面图 G的对偶图,n*,m*,r*和 n
,m,r分别为 G*和 G的顶点数,边数和面数,则
（ 1） n*= r
（ 2） m*=m
（ 3） r*=n
（ 4） 设 G*的顶点 v*i位于 G的面 Ri中,则 dG*(vi*)=deg(Ri)
(1),(2)由 G*的构造可知是显然的。
(3)由于 G与 G*都连通，因而满足欧拉公式,
n-m+r = 2
n*-m*+r* = 2
由 (1),(2))可知,r* = 2+m*-n* = 2+m-r = n
(4)设 G的面 Ri的边界为 Ci,设 Ci中有 k1(k1≥0)条桥,k2个非桥边
，于是
Ci的长度为 k2+2k1,即 deg(Ri)＝ k2+2k1，
k1条桥对应 vi*处有 k1个环,k2条非桥边对应从 vi*处引出 k2条边，
所以 dG*(vi*)＝ k2+2k1＝ deg(Ri)。
证明定理 17.18 设 G*是具有 k（ k?2） 个连通分支的平面图 G的对偶图,n*,m*,r*,n,m,r分别为 G*和 G的顶点数,边数和面数,
（ 1） n*= r
（ 2） m*=m
（ 3） r*=n?k+1
（ 4） 设 G*的顶点 v*i位于 G的面 Ri中,则 dG*(v*i)=deg(Ri)
三,自对偶图定义 17.8 设 G*是平面图 G的对偶图,若 G*?G,则称 G为自对偶图 。
在 n?1(n?4)边形 Cn?1内放置 1个顶点,使这个顶点与 Cn?1上的所有的顶点均相邻,所得 n阶简单图称为 n阶轮图 。 记为 Wn。
n为奇数的轮图称为 奇阶轮图 。
n为偶数的轮图称为 偶阶轮图 。
轮图都是自对偶图 。
小节结束
17.5 图中顶点的着色规定,点着色都是对无环无向图进行的 。
一,关于顶点着色的基本概念定义 17.9
（ 1） 图 G的一种着色 —— 对无环图 G的每个顶点涂上一种颜色,使相邻顶点涂不同的颜色 。
（ 2） 对 G进行 k着色 （ G是 k-可着色的 ） —— 能用 k种颜色给 G
的顶点着色 。
（ 3） G的色数?(G)=k—— G是 k-可着色的，但不是 (k?1)-可着色的。
二,关于顶点着色的几个简单结果定理 17.19?(G)=1当且仅当 G为零图 。
定理 17.20?(Kn)=n。
定理 17.21奇圈或奇阶轮图的色数均为 3,偶阶轮图的色数为 4。
定理 17.22 设 G中至少含有一条边，则?(G)=2当且仅当 G为二部图。
三、色数的上界定理 17.23 对于任意无向图 G,均有?(G)(G)+1。
n=1时,结论成立 。
设 n=k(k≥1)时结论成立,则当 n=k+1时,
设 v为 G中任一个顶点,令 G'=G-v,则 G'的阶数为 k,由假设可知?(G')(G')+1≤Δ(G)+1。
当将 G'还原成 G时,由于 v至多与 G'中 Δ(G)个顶点相邻,而在
G'的点着色中,Δ(G)个顶点至多用了 Δ(G)种颜色,于是在
Δ(G)+1种颜色中至少存在一种颜色给 v涂色,使 v与相邻顶点涂不同颜色 。
证明 提示：对 G的阶数 n作归纳法。
例 17.4 求下面各图的色数。
定理 17.24 (布鲁克斯定理 ) 若连通无向图 G不是 Kn(n?3),也不是奇数阶的圈，则?(G)(G)。
因为 (1)为二部图，由定理 17.22可知,?(G) =2。
(2)为 6阶轮图 W6,由定理 17.21可知,?(G) =4。
由定理 17.24可知,?(G)≤4,又因为 (3)中有奇圈，于是?(G)
≥3,因而?(G)为 3或 4，用 3种颜色不可能给 G4着色，于是只能是?(G) =4。
解答小节结束
17.6 地图的着色与平面图的点着色一,地图与面着色
1,地图与国家定义 17.10
（ 1） 地图 —— 连通无桥平面图的平面嵌入与所有的面 。
（ 2） 国家 —— 地图的面 。
（ 3） 两个国家相邻 —— 两个国家的边界至少有一条公共边 。
有 5个国家，
1与 2相邻,1与 4相邻，
2,3,4均与 5相邻。
5 4 1 2 3
2,地图的面着色定义 17.11
（ 1） 地图 G的一种面着色 —— 对地图 G的每个国家涂上一种颜色,使相邻国家涂不同的颜色 。
（ 2） G是 k-面可着色的 —— 能用 k种颜色给 G的面着色,就称对 G的面进行了 k着色 。
（ 3） G的面色数?*(G)=k—— G是 k-面可着色的,但不是 (k-1)-
面可着色的,即最少用 k种颜色给 G的面着色 。
研究地图的着色可以转化成对它的对偶图的点着色 。说明二,地图的面着色转化成对偶图的点着色定理 17.25 地图 G是 k-面可着色的当且仅当它的对偶图 G*是 k-
点可着色的 。
三,五色定理定理 17.26 任何平面图都是 5-可着色的 。
四色猜想问题,提出来已经近 150年了,但时至今日还没有得到彻底解决 。
小节结束
17.7 边着色本节讨论的图是无环的无向图 。
一,对图 G进行边着色定义 17.12
（ 1） 对图 G边的一种着色 —— 对图 G的每条边涂上一种颜色,
使相邻的边涂不同的颜色 。
（ 2） G是 k-边可着色的 —— 能用 k种颜色给 G的边着色 。
（ 3） G的边色数(G)=k—— 若 G是 k-边可着色的,但不是
(k-1)-边可着色的,即 最少用 k种颜色给 G的边着色 。
二、关于边着色的一些定理定理 17.27 G为简单平面图，则?(G)(G)(G)+1。
该定理是维津定理。
定理说明，对简单图来说，它的边色数 χ‘只能取它的
(G),或者是它的?(G) +1。
究竟哪些图的(G)是?(G),哪些是?(G) +1,至今还是一个没有解决的问题。
定理 17.28
设 G为长度大于或等于 2的偶圈，则 χ'(G)=Δ(G)=2.
设 G为长度大于或等于 3的奇圈，则 χ'(G)=Δ(G)+1=3,
n=4时,由维津定理可知,结论正确 。
n=5时,由维津定理可知,结论正确 。
n≥6时,Δ(Wn)=n-1≥5,Wn中间顶点关联的 n-1条边必须用 n-1
种颜色着色 。
而外圈 Cn-1上的任何边都准确的与其余的 4条边相邻,于是总可以找到 n-1种色中的一种为它涂色,所以 χ'(Wn)≤n-1。
又由维津定理可知,χ'(Wn)≥n-1,所以 χ'(Wn)=n-1。
定理 17.29(Wn) =?(Wn) = n?1,其中 n?4。
定理 17.30 二部图的边色数等于最大度 。
证明定理 17.31
当 n(n?1)为奇数时,(Kn)=n； 当 n为偶数时,(Kn)=n?1。
例 17.5 证明 χ'(W4)=Δ(W4)=3,χ'(W5)=Δ(W5)=4。
由维津定理可知结论是正确的。
解答例 17.6 求下面所示各图的边色数。
小节结束
(1)中无奇长回路，所以它为二部图，由定理 17.30可知
χ'=Δ=4。
由维津定理可知,(2)中 χ'≥Δ=4,又存在 4种颜色的边着色，
所以 χ'≤4,因而 χ'=4。
解答本章主 要内容
平面图及平面嵌入 。
平面图的面与次数 。
极大平面图及性质 。
极小非平面图 。
欧拉公式及其推广 。
平面图的边数 m与顶点数 n的关系 。
简单平面图 G中,δ(G)≤5。
库拉图斯基的两个定理 。
平面图的对偶图 。
本章主 要内容
顶点的着色与点色数 。
关于点色数的一些定理 。
地图及其面着色,面色数 。
平面图的五色定理 。
边着色及边色数 。
关于边着色的一些定理 。
本章学习要求
深刻理解本部分的基本概念：平面图,平面嵌入,平面图的面,次数,极大平面图,极小非平面图,平面图的对偶图,
自对偶图等 。
熟练掌握极大平面的性质,特别是充分必要条件 。
熟练掌握并会应用欧拉公式及其推广形式 。
掌握由欧拉公式及其推广形式所证明的平面的性质 。
会用库拉图斯基定理证明某些图不是平面图 。
掌握平面图与其对偶图某些关系的定理 。
深刻理解点着色,边着色,点色数,边色数的概念 。
理解并记住地图面着色与它的对偶图点着色的关系的定理 。
会应用点色数及边色数解决一些简单的实际问题 。
小节结束
1,设 G 是连通的简单的平面图，面数 r < 12,? ( G )? 3,
（ 1 ）证明 G 中存在次数? 4 的面
（ 2 ）举例说明当 r = 12 时，（ 1 ）中结论不真,
解本题可用的定理有欧拉公式、握手定理、各面次之和与边数的关系等,使用反证法证明,设 G 的阶数、边数、面数分别为 n,m,r,
（ 1 ）否则，由欧拉公式得
2 m > 5 r = 5 ( 2+ m? n ) ①
由于? ( G )? 3 及握手定理又有
2 m? 3 n ②
由 ① 与 ② 得 m? 3 0 ③
又有
r = 2+ m? n < 1 2 ④
由 ④ 及 ② 又可得
m < 30 ⑤
③,⑤ 是矛盾的,
（ 2 ）正十二面体是一个反例,
解只需证明 G 和 G 中至少有一个是非平面图,采用反证法,否则 G 与
G 都是平面图，下面来推出矛盾,
G 与 G 的边数 m,m? 应满足
2
)1(
'
nn
mm （ K
n
的边数） ①
由鸽巢原理知 m 或 m?,不妨设 m,
4
)1(?
nn
m ②
又由定理 1 7,12 知 m? 3 n? 6 ③
由 ② 与 ③ 得 n
2
13 n + 24? 0 ④
由 ④ 解得 2? n? 10 ⑤
⑤ 与 n? 11 矛盾,
其实，当 n = 9,1 0 时，命题结论已真,
2,设 G 是阶数 n? 11 的无向平面图，证明 G 和 G 不可能全是平面图,
证
3,证明图 14 所示图为非平面图图 14
用库拉图斯基定理证明方法一,图 15 所示图为图 14 所示图的子图，它是 K
3,3
（请找出互补顶点子集），由库拉图斯基定理得证命题,
图 15
证方法二,
图 16 所示图为图 14 的子图（删除边 ( a,f ) ），收缩图 16 中 的
( a,e ) 和 ( f,g ) 所得图为 K
5
,由库拉图斯基定理得证命题,
图 16
证证明中用 到 n? 3 的极大平面图的性质，以及平面图与对偶图的关系，对偶图的连通性等,
（ 1 ）证 G * 是 2 - 边连通的,
由 G * 的连通性可知,? ( G *)? 1,又因为 G 为极大平面图，故 G 为简单图，所以 G * 中无桥（因为 G 中无环），
所以,? ( G *)? 2,故 G * 为 2 - 边连通的,
（ 2 ）证 G * 是 3 - 正则图,
易知 G * 为简单图，且每个顶点的度数均为 3 （由定理
17.7 决定），故 G * 为 3 - 正则图,
4,设 G 为 n （ n? 3 ）阶极大平面图，证明 G 的对偶图 G * 是 2 -
边连通的 3 - 正则图,
证
5,求图 17 所示图的点色数?,边色数,以及面色数? *,
图 17
（ 1 ）因为 G 中含奇圈，所以 3,由布鲁克斯定理知 = 4,
又容易证明不能用 3 种颜色涂色：由于 a,b,c 彼此相邻，
因而至少用 3 种颜色涂色，设用颜色?,?,? 分别给 a,b,
c 涂色,此时最省还用这三种颜色给 d,e,f 涂色，而且
d,e,f 也只能用颜色?,? 和?,这样 g 只能用另一种颜色，
比如? 涂色，所以? = 4,
解
（ 2 ）由维津（ V i z i ng ）定理可知 =4 或 5,但可用 4 种颜色给边涂色，见图 18 所示,
图 18
（ 3 ）易知图 17 的对偶图为图 19 所示，容易证明它的点色数为 4,所以图
17 的面色数? *= 4,见图 20 所示,
图 20图 19
用维津定理及握手定理即可证,
由维津定理知 3 =? ( G ) ( G ) ( G ) + 1 = 4,下面只需证可用 3 种颜色给 G 的边着色,设 C 为 G 中的哈密顿回路，则 C 为偶圈（ 3 n =2 m ），所以用两种颜色可给 C 的边着色,G 中不在 C 上的边彼此不邻（为什么？），因而用第 3 种颜色给它们着色即可,
6,设 G 为 3 - 正则的哈密顿图，证明( G ) = 3,
证
7,某校计算机系三年级学生在本学期共选 6 门选修课 C
i
,
i = 1,2,…,6,
设 S ( C
i
) 为选 C
i
课的学生集,已知
S ( C
i
)? S ( C
6
),i = 1,2,…,5,
S ( C
i
)? S ( C
i +1
),i = 1,2,3,4,
S ( C
5
)? S ( C
1
),
问这 6 门课至少几天能考完？
由已知条件做无向图 G =< V,E >,
其中 V ={ C
1
,C
2
,…,C
6
},
E = {( Ci,Cj ) | S ( C
i
)? S ( C
j
) },
见图 21 所示 W
6
,
给 G 一种着色（点着色）,
C
i
与 C
j
着同色
C
i
与 C
j
不相邻
没有学生既学 C
i
又学 C
j
C
i
与 C
j
可同时考,
图 21
于是最少的考试时间为
( G ) = 4 （见定理 17.2 1 ）,
解小节结束作业习题十七,
1,3,15,24,26,29
结束
