图论讲义第7章-平面图

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) Kn ( n≤4 ) 和 K1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图G是简单图。 定义7.1.2 设图G是平面图 (已平面嵌入)，G的边将平面划分出的若干区域都称为图G的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面R 的次数记为deg(R)。

定理7.1.4 平面图G中所有面的次数之和等于G的边数的两倍，即

其中R1, R2, … , Rr是G的所有面。 证明： 对G的任何一条边e，若e是两个面 Ri 和 Rj 的公共边界，则在计算Ri

和 Rj 的次数时，e各提供了1；若e只是某一个面的边界，则在计算该面的次数时，e提供了2。可见每条边在计算总次数时，都提供2。因而结论成立。

1deg()2().riiRGε==∑ 2

定义7.1.3 设G为简单平面图，若在G的任意不相邻的顶点u, v之间加边uv 后，所得之图成为非平面图，则称G是极大平面图。

易见K1, K2, K3, K4, K5– 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 的连通分支分别为G1, G2, …, Gw，并设Gi 的顶点数、边数和面数分别为ni, mi, ri 。由欧拉公式可知 3

定理7.2.3 设G是连通的平面图，且每个面的次数至少为 l (l ≥ 3)，则G的边数 m 与顶点数 n 有如下关系：

(2).2lmnl≤−−

证明：由定理7.1.4可知

推论7.2.1 K5 和 K3,3 都不是平面图。 证明：若 K5 是平面图，由于K5中无环边和重边，故每个面的次数至少为3，而 K5 的边数为10。由定理7.2.3，应有 , 这是不可能的。因此K5不是平面图。

若K3,3是平面图，由于K3,3中最短圈的长度为4，故每个面的次数至少为

4，而K3,3的边数为9。由定理7.2.3，应有 , 这是不可能的。

因此K3,3不是平面图。证毕。

推论7.2.2 Kn (n ≥ 5)和K3,n (n ≥ 3)都不是平面图。 证明：由定理7.1.2和推论7.2.1立即可知。 推论7.2.3 K5 和 K3,3都是极小非平面图。

由推论7.2.1和极小非平面图的定义容易验证。

定理7.2.4 设G是具有w(w≥1)个连通分支的平面图, 各面的次数至少为l(l ≥3)，则G的边数m与顶点数n有如下关系：

证明：利用欧拉公式的推广形式(定理7.2.2)，与上一定理类似可证。

11111112,(1,2,).,.,,1,2()1iiiwwiiiiwiiwwwwiiiiiiiiiinmriwmmnnGGGrrwwnmrnmrnmrw=======

−+=====−+=−+=−+=−++−∑∑∑∑∑∑∑󰀢易知由于的每个分支有一个外部面而只有一个外部面

故的面数于是

整理即得结论. 证毕.

12deg()2.,2(2),riimRlrrmnmlmn==≥⋅=+−≥+−∑ 由欧拉公式可知将此式代入上式得整理便得结论。证毕。

310(52)932≤−=

−

49(62)842≤−=

−

(1).2lmnwl≤−−− 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的某个面Ri的次数deg(Ri)=s ≥ 4，则Ri的边界上至少有4个顶点，设其中4个依次相邻的顶点为v1, v2, v3, v4。若v1与v3在G中不相邻，则在Ri内添加边v1v3不破坏平面性，这与G是极大平面图矛盾。因而v1与v3

在G中必定相邻。但因面Ri的存在，边v1v3必在Ri的外边。类似地，v2与v4在

G中也必定相邻且边v2v4必在Ri的外边。于是边v1v3与边v2v4必在Ri的外部相

交。这与G是平面图矛盾。从而G中各面的次数不会大于3。 证毕。

由该定理可知，下列平面图中，只有(c)是极大平面图。

2122lll=+−−

(1)3(2)36.2lmnwnnl≤−−≤−=−−

12deg()3riimRr===∑

(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 若两个图G1和G2同构，或者G1和G2经过反复插入或消去2度顶点后同构，则称G1和G2是同胚的。

例如，下列(a)与K3 同胚，(b)与K4 同胚。

下列两个定理是平面图判定定理，证明从略。 定理7.3.1 (库拉托夫斯基定理1) 图G是平面图当且仅当G中既不含与K5 同胚的子图，也不含与 K3,3 同胚的子图。

定理7.3.2 (库拉托夫斯基定理2) 图 G 是平面图当且仅当 G 中既没有可收缩到 K5 的子图，也没有可收缩到K3,3的子图。

12deg()3riimRr===∑12()6.niimdvn==≥∑

(b) (a)