返回：0100 离散数学课程总目录 · 上一章：0109 图的矩阵表示 · 下一章：0111 图着色

1、资料来源与学习目标

本章对应刘田老师平面图部分，Auto_Tutor 中包含 10.1 到 10.5 的课件、习题课、习题十一和答案。核心目标是把“能否无交叉画图”转化为欧拉公式、面次数、禁用子图和对偶图的判断。

本章主线：平面嵌入 -> 面 -> 欧拉公式 -> 边数上界 -> 非平面判定。

2、颜色标注

颜色 含义
粉色 必背公式和判定定理
蓝色 核心概念
橙色 易错边界
绿色 证明线索

3、核心概念

概念 定义
平面图 已画在平面上，边只允许在公共端点相交的图
可平面图 存在某种平面嵌入的图
平面嵌入 把图画到平面上且没有非端点交叉
面 平面图中不含顶点和边的极大连通区域及其边界
外部面 面积无界的面
面次数 面边界长度，桥要在同一面边界上计两次
极大平面图 已是平面图，任意两个不相邻点之间加边都会破坏平面性
极小非平面图 非平面图，删任意一条边后变成平面图

4、欧拉公式与边数上界

连通平面图欧拉公式：

1
n - m + r = 2

一般平面图若有 p 个连通分支：

1
n - m + r = 1 + p

面的握手定理：

1
sum deg(R_i) = 2m

若连通平面图每个面的次数至少为 l >= 3，则：

1
m <= (n-2)l/(l-2)

简单平面图最常用上界：

1
n >= 3 时，m <= 3n - 6

简单极大平面图：

1
2
n >= 3 时，m = 3n - 6
每个面的次数都是 3

简单平面图还必有：

1
delta(G) <= 5

m <= 3n-6 只适用于 n>=3 的简单平面图。判断 K_{3,3} 时要用二部图无奇圈，所以每个面次数至少为 4，得到 m <= 2n-4。

5、非平面图判定

K5 非平面：

1
2
n=5, m=10
若平面，则 m <= 3n-6 = 9，矛盾。

K3,3 非平面：

1
2
3
n=6, m=9
二部图无奇圈，面次数至少 4。
若平面，则 m <= 2n-4 = 8，矛盾。

Kuratowski 定理：

1
2
G 是平面图
<=> G 不含与 K5 或 K3,3 同胚的子图。

边收缩版本：

1
2
G 是平面图
<=> G 不含可以边收缩到 K5 或 K3,3 的子图。

6、平面性判定流程

做题时可以按下面顺序判断：

1
2
3
4
5
6
1. 先看是否简单图、连通图，确认能不能直接用 m<=3n-6。
2. 若是二部图或无三角形图，改用每个面次数至少 4，得到 m<=2n-4。
3. 若题目给面次数下界 l，使用 m <= (n-2)l/(l-2)。
4. 若边数上界不能推出矛盾，再找 K5 或 K3,3 的同胚子图。
5. 若同胚子图不明显，尝试边收缩到 K5 或 K3,3。
6. 若要证明极大平面图，常用“任意加边都会违反 m<=3n-6”。

K5/K3,3 的判定不要求原图本身就是它们，只要含同胚子图，或者含可收缩到它们的子图，就能判非平面。

常见结论速查：

条件 可用结论
简单平面图，n>=3 m<=3n-6
简单二部平面图，n>=3 m<=2n-4
极大平面图，n>=3 m=3n-6，每个面都是三角形
简单平面图 必有顶点度数不超过 5
平面图非连通，分支数 p n-m+r=1+p

7、对偶图与外平面图

对偶图 G*：

1
2
3
G 的每个面对应 G* 的一个顶点；
G 的每条边对应 G* 的一条边；
若原边分隔两个面，则对偶边连接这两个面的对偶顶点。

基本性质：

1
2
3
4
5
6
n* = r
m* = m
r* = n - p + 1
G* 是连通平面图
环与桥互为对偶
deg_{G*}(v_i*) = deg_G(R_i)

对偶图依赖具体平面嵌入。两个同构的平面图如果嵌入不同，对偶图不一定同构。

外平面图：

1
存在一种平面嵌入，使所有顶点都在同一个面的边界上。

外平面图判定：

1
2
G 是外平面图
<=> G 不含与 K4 或 K2,3 同胚的子图。

极大外平面图：

1
2
3
4
5
6
7
所有顶点在外部面边界上；
外部面边界是 n-圈；
所有内部面边界是 3-圈；
m = 2n - 3；
有 n-2 个内部面；
至少 3 个顶点度数 <= 3；
至少 2 个 2 度顶点。

外平面图常见判定流程：

1
2
3
4
1. 先尝试画出所有顶点都在外部面的嵌入。
2. 如果图含 K4 或 K2,3 的同胚子图，则不是外平面图。
3. 极大外平面图可以用 m=2n-3 快速检查。
4. 若 n>=3 的极大外平面图没有 2 度顶点，必然有问题。

8、平面哈密顿图

Tait 猜想曾认为：

1
3 连通 3 正则平面图都是哈密顿图。

后来被 Tutte 图和 Lederberg 图反驳。已知充分条件：

1
4 连通平面图是哈密顿图。

Grinberg 必要条件：若简单平面哈密顿图的哈密顿回路内外部次数为 i 的面数分别为 r_i'、r_i''，则：

1
sum_{i>=3} (i-2)(r_i' - r_i'') = 0

这个条件常用来证明某些平面图不是哈密顿图，或不存在经过指定边的哈密顿回路。

使用 Grinberg 条件时的模板：

1
2
3
4
1. 假设存在哈密顿回路 C。
2. 统计 C 内部和外部不同次数的面数。
3. 代入 sum(i-2)(r_i' - r_i'')=0。
4. 若推出整数不可能、奇偶矛盾或模意义矛盾，则不存在这样的 C。

Grinberg 条件是必要条件，不是充分条件。满足该等式不能推出一定存在哈密顿回路。

9、习题与答案

习题 11.6

设 G 是 n=7, m=15 的简单连通平面图，证明 G 为极大平面图。

证明：G 不是完全图，所以存在不相邻顶点 u,v。若加边得 G'=G+(u,v) 仍平面，则：

1
2
n'=7, m'=16
m' <= 3n' - 6 = 15

矛盾。因此任何可加边都会破坏平面性，G 是极大平面图。

习题 11.7

设 G 是 n>=11 阶无向简单图，证明 G 或补图 Gbar 必为非平面图。

只需看 n=11。K_11 有 55 条边，G 与 Gbar 总边数为 55，所以至少一个边数 m>=28。若它平面，则：

1
m <= 3n - 6 = 27

矛盾。

习题 11.12

若 G 是 n>=4 阶极大平面图，则对偶图 G* 是 2-边连通的 3-正则图。

答案要点：

1
2
3
极大平面图每个面都是三角形 => G* 每个顶点度为 3。
G 中无环 => G* 中无桥；且 G* 连通 => G* 2-边连通。
G 中无桥且每个面次数为 3 => G* 无平行边，是简单 3-正则图。

习题 11.16

G 是连通 3-正则平面图，r_i 是 i 次面的个数，证明：

1
12 = 3r3 + 2r4 + r5 - r7 - 2r8 - 3r9 - ...

证明线索：

1
2
3
4
3n = 2m
2m = sum_{i>=3} i r_i
r = sum_{i>=3} r_i
n - m + r = 2

把 n=2m/3 代入欧拉公式并整理：

1
sum_{i>=3} (6-i)r_i = 12

即所求式。

习题 11.17

设 G 是 n>=7 阶外平面图，证明补图 Gbar 不是外平面图。

答案思路：只需验证 n=7 的极大外平面图。7 阶极大外平面图在同构意义下有 4 种；它们的补图虽然仍可平面嵌入，但无法使所有顶点同时位于同一个面的边界上，因此不是外平面图。n>7 时含 7 阶情形作为子结构，结论继承。

习题 11.18

图 11.17(b) 是哈密顿图，但不存在既含 e1 又含 e2 的哈密顿回路。

答案中给出一条哈密顿回路：

1
e3 e15 e14 e13 e12 e2 e7 e8 e9 e10

反证若存在同时含 e1,e2 的哈密顿回路 C，则 e3 必在 C 上；e10,e15 不能同时在 C 上，e6,e11 也不能同时在 C 上。为了保证相关顶点度为 2，只能迫使 e10,e11 或 e6,e15 进入 C。取 e10,e11 情形，会继续推出 e14,e7,e4,e13 在 C 上，形成小圈：

1
e3 e10 e1 e14 e13 e4 e7 e2 e11

导致有顶点不能进入哈密顿回路，矛盾。

10、复盘清单

1
2
3
4
5
6
7
1. 会区分平面图、可平面图和平面嵌入。
2. 会用 n-m+r=2 和 sum deg(R)=2m。
3. 会推出 m<=3n-6 与 K5、K3,3 非平面。
4. 会用极大平面图的“每个面是三角形”。
5. 会写对偶图的 n*,m*,r* 和环/桥对偶关系。
6. 会判断外平面图和极大外平面图。
7. 知道 Grinberg 条件用于排除哈密顿回路。