集合与图论学习笔记07

定义

定义 7.1 平面图

若一个图能画在平面上使得它的边互不相交（除了在顶点处外），则称该图为平面图，或称该图为能嵌入平面的。

本文中把图 \(G\) 的平面嵌入称为平图

给出有关 \(Jordan\) 曲线的一个定理但不加以证明（涉及到拓扑相关知识）：

定理 7.1.1 (Jordan 曲线定理)

设 \(J\) 是平面上的一条 \(Jordan\) 曲线，平面的剩下部分被分割为两个不相交的开集，称为 \(J\) 的内部和外部，分别记为 \(int(J)\) 和 \(ext(J)\)

分别记它们的闭包为 \(Int(J)\) 和 \(Ext(J)\)，显然 \(Int(J) \cap Ext(J) = J\)

则：链接 \(int(J)\) 和 \(ext(J)\) 的点的任何连线必在某个点和 \(J\) 相交

可以仿照平面图的定义来定义可嵌入曲面 \(S\) 的图

不加以证明的给出定理

定理 7.1.2

对于任意一个曲面 \(S\) ，总存在不可嵌入 \(S\) 的图

定理 7.1.3

每个图都可以嵌入三维空间 \(\mathbb{R}^3\)

定理 7.1.4

图 \(G\) 可嵌入平面当且仅当它可嵌入球面

根据 \(Jordan\) 曲线定理可以证明：\(K_5\) 和 \(K_{3,3}\) 不是平面图

定理 7.1.5 常见非平面图

图 \(K_5\) 和 \(K_{3,3}\) 不是平面图

证明： 点击查看证明

先证明 \(K_5\) 不是平面图

假设 \(K_{5}\) 是平面图。设顶点 \(v_1,v_2,v_3,v_4,v_5\)，圈 \(C=v_1v_2v_3v_1\) 是一条 \(Jordan\) 曲线，\(v_4\in int(C)\) 或 \(v_4\in ext(C)\)

不妨设 \(v_4\in int(C)\)，则 \(v_4v_1\) ，\(v_4v_2\)，\(v_4v_3\) 三条边均在 \(int(C)\) 中，分为三个区域 \(intC_1,intC_2,intC_3\)

此时 \(v_5\) 必定在 \(ext(C),intC_1,intC_2,intC_3\) 中，此时 \(v_5\) 与 \(v_1,v_2,v_3,v_4\) 之间的边必有一条与其他边相交，矛盾

证明 \(K_{3,3}\) 不是平面图

假设 \(K_{3,3}\) 是平面图。设顶点集为 \(u_1,u_2,u_3\) 和 \(v_1,v_2,v_3\)，圈 \(C=u_1v_1u_2v_2u_1\) 是一条 \(Jordan\) 曲线，\(v_3\in int(C)\) 或 \(v_3\in ext(C)\)

不妨设 \(v_3\in int(C)\)，则 \(v_3u_1\) 和 \(v_3u_2\) 两条边均在 \(int(C)\) 中，分为两个区域 \(intC_1,intC_2\)

此时 \(u_3\) 必定在 \(ext(C),intC_1,intC_2\) 中，此时 \(u_3\) 与 \(v_1,v_2,v_3\) 之间的边必有一条与其他边相交，矛盾

\(K_5\) 是可环面嵌入的，\(K_{3,3}\) 是可 \(Mobius\) 带嵌入的

定义 7.2 面、对偶图

一个图 \(G\) 把平面划分为若干个连通区域，这些区域的闭包称为 \(G\) 的面，其中恰有一个无界的面，称为外部面

平图 \(G\) 的几何对偶图 \(G^*\) 定义如下

• 在每个面内取一个点作为 \(G^*\) 的顶点
• 对于 \(G\) 的每一条边 \(e\) ，在 \(G^*\) 中连接 \(e\) 所在的两个面的对应顶点，并使该边与 \(e\) 相交于一点

显然， \(G^*\) 有多重边当且仅当\(G\) 中存在两个面至少有两条公共边

\(G^*\) 面数量 \(f^*=n\)，顶点数量 \(n^*=f\)，边数量 \(e^*=e\)

定理 7.2.0 欧拉公式

若 \(G\) 是连通平图，则 \(n-e+f=2\)

证明： 点击查看证明

对 \(f\) 使用数学归纳法：

\(f=1\) 时，\(G\) 是一棵树，\(e=n-1\)，所以 \(n-e+f=2\)

假设当 \(f\le k\) 时结论成立，现证明当 \(f=k+1\) 时结论也成立：

任选 \(G\) 的一条不是割的边 \(e\) ，则 \(G-e\) 时连通平图，根据归纳假设有 \(n-(e-1)+(f-1)=2\)

即 \(n-e+f=2\) 成立

定理 7.2.1

两个同构的平图的对偶图不一定同构

给出图示

由于一个平面图可以存在不同的平面嵌入，因此它的对偶图也可能不唯一，所以不把对偶图的概念扩展到平面图上

定理 7.2.2

\(G\) 是平图，则 \(\sum_{f\in F}d(f)=2e\)

证明： 点击查看证明

考虑对偶图 \(G^*\) ，则 \(\sum_{f\in F}d(f)=\sum_{v\in V(G^*)}d(v)=2e^*=2e\)

定理 7.2.3

平图 \(G\) 的对偶图 \(G^*\) 的对偶图同构于 \(G\)

证明： 点击查看证明

只需要证明 \(G\) 和 \(G^{**}\) 之间存在同构映射 \(\phi\) ：\(V(G)\rightarrow V(G^{**})\)

对于 \(G\) 的每个顶点 \(v\) ，考虑 \(G\) 中以 \(v\) 为端点的所有边，这些边在 \(G^*\) 中对应于若干条边，这些边将 \(G^*\) 分成若干个面，这些面的对应顶点构成 \(G^{**}\) 中的一个顶点，定义 \(\phi(v)\) 为该顶点

下面证明 \(\phi\) 是同构映射

设 \(u,v\in V(G)\) ，\(uv\in E(G)\) ，则 \(uv\) 在 \(G^*\) 中对应于一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(\phi(u)\) 和 \(\phi(v)\) ，因此 \(\phi(u)\phi(v)\in E(G^{**})\)

反之，设 \(\phi(u),\phi(v)\in V(G^{**})\) ，\(\phi(u)\phi(v)\in E(G^{**})\) ，则 \(G^*\) 中存在一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(u\) 和 \(v\) ，因此 \(uv\in E(G)\)

若一个平图和它的对偶图同构，则称该平图为自对偶图

定理 7.2.4

若 \(G\) 是自对偶平图，则 \(2n=e+2\)

证明： 点击查看证明

由于 \(G\) 是自对偶平图，则 \(n=f\) 且 \(e=e^*\)

由欧拉公式 \(n-e+f=2\) 可得 \(2n=e+2\)

定理 7.2.5

欧拉平图的对偶图是二分图（偶图）

证明： 点击查看证明

设 \(G\) 是欧拉平图，\(G^*\) 是 \(G\) 的对偶图

由于 \(G\) 是欧拉图，则 \(G\) 的每个顶点的度数均为偶数

\(G\) 的每一个顶点对应 \(G^*\) 的一个面，则面度数（即围成面的边数）也为偶数

定理 7.2.6

\(G\) 是平图，\(G^{**}\) 和 \(G\) 同构当且仅当 \(G\) 连通

证明： 点击查看证明

设 \(G\) 是平图，\(G^{**}\) 是 \(G\) 的对偶图的对偶图

必要性：

设 \(G\) 不连通，则 \(G\) 有两个连通分支 \(G_1\) 和 \(G_2\)

则 \(G^*\) 有一个面 \(f\) ，该面对应于 \(G^{**}\) 中的一个顶点 \(v\) ，且 \(v\) 与 \(G^{**}\) 中的其他顶点均不相连

因此 \(G^{**}\) 不连通，矛盾

充分性：

设 \(G\) 连通，则对于 \(G\) 的任意一条边 \(e\) ，\(e\) 不是割边

则 \(G^*\) 中与 \(e\) 对应的边 \(e^*\) 连接 \(G^*\) 中的两个不同顶点

因此 \(G^{**}\) 中与 \(e^*\) 对应的边 \(e^{**}\) 连接 \(G^{**}\) 中的两个不同顶点

定义映射 \(\phi:V(G)\rightarrow V(G^{**})\) ，对于 \(G\) 的每个顶点 \(v\) ，\(\phi(v)\) 是 \(G^{**}\) 中与 \(v\) 对应的顶点

下面证明 \(\phi\) 是同构映射

设 \(u,v\in V(G)\) ，\(uv\in E(G)\) ，则 \(uv\) 在 \(G^*\) 中对应于一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(\phi(u)\) 和 \(\phi(v)\) ，因此 \(\phi(u)\phi(v)\in E(G^{**})\)

反之，设 \(\phi(u),\phi(v)\in V(G^{**})\) ，\(\phi(u)\phi(v)\in E(G^{**})\) ，则 \(G^*\) 中存在一条边 \(e^*\) ，该边将 \(G^*\) 分成两个面，这两个面的对应顶点分别为 \(u\) 和 \(v\) ，因此 \(uv\in E(G)\)

定理 7.2.7

\(G\) 是一个平图，每个面至少由 \(k(k\ge 3)\) 条边围成，则 \(e\le \max \{\frac{k(n-2)}{k-2},3n-6\}\)

证明： 点击查看证明

首先证明 \(e \le 3n-6\)

由于每个面至少由 \(3\) 条边围成，则由定理 7.2.2 有 \(\sum_{f\in F}d(f)=2e\ge 3f\)

即 \(f\le \frac{2e}{3}\)

由欧拉公式 \(n-e+f=2\) 可得 \(n-e+\frac{2e}{3}\ge 2\)

即 \(e\le 3n-6\)

其次证明 \(e \le \frac{k(n-2)}{k-2}\)

由于每个面至少由 \(k\) 条边围成，则由定理 7.2.2 有 \(\sum_{f\in F}d(f)=2e\ge kf\)

即 \(f\le \frac{2e}{k}\)

由欧拉公式 \(n-e+f=2\) 可得 \(n-e+\frac{2e}{k}\ge 2\)

即 \(e\le \frac{k(n-2)}{k-2}\)

综上所述，\(e\le \max \{\frac{k(n-2)}{k-2},3n-6\}\)

定理 7.2.8 \(Kuratowski\) 定理

图 \(G\) 是平图当且仅当 \(G\) 不包含 \(K_5\) 或 \(K_{3,3}\) 的剖分

证明待补充

引理 7.2.8.1

若 \(G\) 是非平面图，则 \(G\) 的每个剖分图也是非平面图

引理 7.2.8.2

若 \(G\) 是平面图，则 \(G\) 的每一个子图都是平面图

设 \(G\) 是有两顶点割的图。则存在不重子图 \(G_1\) 和 \(G_2\) 使得 \(V(G_1)\cap V(G_2)=\{u,v\}\) 以及 \(G_1\cup G_2= G\)，把 \(G\) 分成这样的两个子图，在 \(G_1\) 和 \(G_2\) 中用一条新边 \(e\) 链接 \(u\) 和 \(v\) ，得到图 \(H_1\) 和 \(H_2\) ，显然 \(G=(H_1\cup H_2)-e\)

引理 7.2.8.3

若 \(G\) 是非平面图。则 \(H_1\) 和 \(H_2\) 中至少有一个是非平面图

引理 7.2.8.4

设 \(G\) 是非平面的连通图，它不包含 \(K_5\) 和 \(K_{3,3}\) 的剖分图，且有尽可能少的边数，则 \(G\) 是 3-连通的简单图

定义 7.3 平面三角剖分图

每个面的度为 \(3\) 的平图称为平面三角剖分图

定理 7.3.1

每个简单平图都是某个简单平面三角剖分图的生成子图

证明： 点击查看证明

设 \(G\) 是简单平图，若 \(G\) 不是三角剖分图，则存在一个面的度 \(d(f)\ge 4\)

任选该面 \(f\) 的两条不相邻的边 \(uv\) 和 \(wx\) ，在 \(f\) 内部加入一条边 \(uw\) ，则得到一个新的简单平图 \(G'\) ，且 \(G\) 是 \(G'\) 的生成子图

重复上述过程，直到得到一个平面三角剖分图 \(G''\) ，则 \(G\) 是 \(G''\) 的生成子图

定理 7.3.2

任何平面三角剖分图 \(G\) ，都包含一个有 \(\frac{2e}{3}\) 条边的偶子图

为了方便考虑，下面的图都没有自环和多重边

定义 7.4 顶点着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两个顶点着不同颜色，则称为 \(G\) 的一个 \(k\)-着色，着色数 \(\chi(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi(G)=k\) 则称 \(G\) 是 \(k\) 色的

若对 \(k\) 色的图 \(G\) 的每个真子图 \(H\) ，都有 \(\chi(H)<\chi(G)\) ，则称 \(G\) 是 \(k\)-临界图

定理 7.4.1

若 \(G\) 是 \(k\) 临界图，则 \(\delta \ge k-1\)

证明： 点击查看证明

反证法：

设顶点 \(v\) 为 \(G\) 中度数最小的顶点，且 \(d(v)<k-1\)

由于 \(G\) 是 \(k\) 临界的，则 \(G-v\) 是 \((k-1)\) 色的

由于 \(\delta<k-1\) 则 \(v\) 的邻接顶点中最多有 \(k-2\) 种颜色，因此可以给 \(v\) 着上剩下的一种颜色，从而得到 \(G\) 的一个 \((k-1)\)-着色，矛盾

根据定理 7.4.1 可得：每个 \(k\) 色图至少有 \(k\) 个度不小于 \(k-1\) 的顶点

定理 7.4.2

对任意图 \(G\) 有 \(\chi \le \Delta+1\)

证明： 点击查看证明

\(G\) 是 \(k\) 色的，由于每个 \(k\) 色图，至少有 \(k\) 个度不小于 \(k-1\) 的顶点，则 \(\Delta \ge k-1\)，即 \(k \le \Delta+1\)

定理 7.4.3

临界图的顶点割不是团

证明： 点击查看证明

反证法：

设 \(G\) 是临界图，且 \(S\) 是 \(G\) 的一个顶点割，\(S\) 是一个团

记 \(G\) 的连通分支为 \(G_1,G_2,\ldots,G_k\) ，则 \(G-S\) 有 \(k\) 个连通分支

由于 \(G\) 是 \(k\) 临界的，则每个 \(G_i\) 都是 \((k-1)\) 色的

由于 \(S\) 是团，则 \(S\) 中的每个顶点都与 \(G_i\) 中的每个顶点相连，因此 \(G_i\cup S\) 是 \(k\) 色的

则 \(G\) 是 \(k\) 色的，矛盾

定理 7.4.4

每个临界图都是块

证明： 点击查看证明

若 \(v\) 是割点，则 \(\{v\}\) 是一个顶点割，由定理 7.4.3 可知 \(\{v\}\) 不是团，矛盾

定理 7.4.5

设 \(G\) 具有 \(2\) 顶点割 \(\{u,v\}\) ，则 \(d(u)+d(v)\ge 3k-5\)

证明： 点击查看证明

设 \(H_1=G_1+uv\)，\(H_2=G_2 \cdot uv\)

则 \(d_{H_1}(u)+d_{H_1}(v)\ge 2k-2\)

且 \(d_{H_2}(w)\ge k-1\)

这里 \(w\) 是将 \(u\) 和 \(v\) 合并后的新顶点

则 \(d_G(u)+d_G(v)=d_{H_1}(u)+d_{H_1}(v)+d_{H_2}(w)\ge 3k-5\)

定理 7.4.6 Brooks 定理

若 \(G\) 是连通图，且既不是完全图也不是奇环，则 \(\chi(G)\le \Delta\)

证明： 点击查看证明1

设 \(G\) 是满足定理的 \(k\) 色图

不妨假定 \(G\) 是 \(k\) 临界的，则 \(G\) 是一个块，由于 \(1、2\) 临界图都是完全图， \(3\) 临界图是奇环，则 \(k\ge 4\)

若 \(G\) 有 \(2\) 顶点割

由上面可知 \(d(u)+d(v)\ge 3k-5\) ，则 \(\Delta \ge \frac{3k-5}{2}>k-1\)

设 \(G\) 是 \(3\) 连通的

（待补充）

证明： 点击查看证明2

贪心染色法

设图 \(G\) 满足 \(k=\Delta\)，当 \(k\le1\) 时，图 \(G\) 是平凡图，显然成立，当 \(k=2\) 时，图 \(G\) 是路径或环，显然成立

下面证明当 \(k\ge 3\) 的结论

当 \(G\) 不是一个 \(k\) 正则图时

则存在一个顶点 \(v_n\) ，使得 \(d(v_n)<k\)

由于 \(G\) 是连通图，从 \(v_n\) 开始由远及近地给图 \(G\) 的顶点编号为 \(v_n,v_{n-1},\ldots,v_1\) ，则对于每个顶点 \(v_i(i <n)\) ，它的邻接顶点中至多有 \(k-1\) 个顶点的编号小于 \(i\) ，也就是说，至少有一个节点的邻居的编号比这个节点大

现在按照 \(v_1,v_2\ldots v_n\) 的顺序染色，在处理 \(v_i\) 时，至少有一个邻居是未染色的，，已染色的邻居数量至少只有 \(d(v_i)-1\) 个，所以至少可以找出 1 中颜色给该节点染色

当 \(v_n\) 染色时，由于 \(d(v_n)<=k\) 所以也至少可以找出一种颜色染色，故成立

当 \(G\) 是正则图时，若 \(G\) 有割点 \(x\)

以割点 \(x\) 为界，把 \(G\) 分成若干个子图 \(G_1,G_2,\ldots,G_m\) ，则每个子图 \(G_i\) 都不是 \(k\) 正则图

对每个子图 \(G_i\) ，按照上面的方法给它染色，然后把这些子图重新连接起来，由于割点 \(x\) 在每个子图中都有一个颜色没有使用，所以可以给割点 \(x\) 染色，故成立

若 \(G\) 是 2 连通图

寻找这样的顶点 \(v_1,v_2,v_n\) 满足 \(v_1,v_2\) 都是 \(v_n\) 的邻接点，且 \(G-v_1-v_2\) 是连通的并且 \(v_1\) 和 \(v_2\) 之间没有边

若找到了这样的顶点，用下面的方法染色

\(v_1,v_2\) 同种颜色，在删去后，此时可以用 \(k-1\) 种颜色给 \(G-v_1-v_2\) 染色，处理 \(v_n\) 时，由于 \(v_1,v_2\) 同种颜色，所以 \(v_n\) 的邻接点中至多有 \(k-1\) 个颜色被使用，因此至少有一种颜色可以给 \(v_n\) 染色，故成立

下面证明可以找到这样的顶点

若存在这样的顶点 \(x\) ，使得 \(G-x\) 是 \(2\) 连通的

设 \(v_1=x\)，在 \(x\) 附近一定能找到一个距离为 2 的点（即 \(x\) 的邻居的邻居，但不直接连着 \(x\)），设为 \(v_2\)。此时 \(v_1, v_2\) 不相邻。

设 \(v_n\) 是 \(v_1\) 和 \(v_2\) 的公共邻居。因为 \(G-v_1\) 是 2-连通的，删去 \(v_1\) 后图是连通的；再删去 \(v_1\) 的一个点 \(v_2\) 后，根据 2-连通的定义，\(G - \{v_1, v_2\}\) 依然连通。

若对于任意顶点 \(x\)，\(G-x\) 都有割点即 \(G-x\) 不是 2-连通的

定义块：图中一个极大的连通子图，且该子图中没有割点。

叶块：在连通图中，如果一个块只包含一个割点，则称该块为叶块。任何包含割点的连通图至少有两个叶块。

设 \(v_n = x\)。由于 \(G-x\) 有割点，它至少有两个叶块 \(B_1, B_2\)。

因为原图 \(G\) 是 2-连通的，顶点 \(x\) 必须与每个叶块中“非割点”的部分有邻居。从 \(B_1\) 中选一个 \(x\) 的邻居 \(v_1\)，从 \(B_2\) 中选一个 \(x\) 的邻居 \(v_2\)。

这样 \(v_1,v_2\) 不连通且删去后不破坏 \(G-x\) 剩余部分的连通性，且 \(x\) 保持与各块连接。因此 \(G - \{v_1, v_2\}\) 连通。

找到了需要的点。

综上原定理成立

色多项式待补充

定义 7.5 边着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两条边着不同颜色，则称为 \(G\) 的一个 \(k\)-边着色，着色数 \(\chi'(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi'(G)=k\) 则称 \(G\) 是 \(k\) 边色的

很显然，有 \(\chi' \ge \Delta\)

证明： 点击查看证明

与最大度顶点 \(v\) 相关联的 \(d(v)=\Delta(G)\) 条边必须两两不同色，因此至少需要 \(\Delta(G)\) 种颜色

定理 7.5.1

若 \(G\) 是二分图则 \(\chi'=\Delta\)

证明： 点击查看证明

只需要证明 \(\chi'(G) \le \Delta(G)\) 即可

对 \(G\) 的边数 \(|E|\) 进行归纳

当 \(|E|=0\) 或 \(|E|=1\) 时，\(\Delta(G)\) 为 0 或 1，\(\chi'(G)\) 也为 0 或 1，定理显然成立

假设对于任何边数少于 \(m\) 的二分图 \(H\)，都有 \(\chi'(H) = \Delta(H)\)，当 \(G\) 有 \(|E|=m\) 条边时

若 \(G\) 是 \(k\) 正则二分图，由于 \(k\) 正则二分图都有完美匹配（见10节的证明），可以将完美匹配中的所有边染成同一种颜色，然后移除这些边，剩下的图是 \(k-1\) 正则二分图，重复 \(k\) 次，则有 \(\chi'(G) = k = \Delta(G)\)

若 \(G\) 不是 \(k\) 正则二分图，采用反证法

若 \(\chi'(G) > \Delta(G)\)

选取 \(G\) 中任意一条边 \(e=(u,v)\)，考虑图 \(G' = G - e\)。显然 \(\Delta(G') \le \Delta(G)\)

根据归纳假设，图 \(G'\) 存在一个 \(\Delta(G)\)-边着色，记 \(\Delta(G) = k\)。

在图 \(G'\) 中，由于删去了边 \(e\)，点 \(u\) 和 \(v\) 的度数都至多为 \(k-1\)。因此在 \(k\) 种颜色中：点 \(u\) 至少缺少一种颜色，记为 \(\alpha\)，点 \(v\) 至少缺少一种颜色，记为 \(\beta\)

若 \(\alpha = \beta\)，则直接用颜色 \(\alpha\) 给边 \(e\) 着色，即得到 \(G\) 的 \(k\)-边着色，得证。

若 \(\alpha \neq \beta\)

考虑 \(G'\) 中仅由颜色 \(\alpha\) 和 \(\beta\) 构成的子图 \(H_{\alpha\beta}\)

\(H_{\alpha\beta}\) 的每个顶点度数至多为 2，因此其连通分支只能是路径或偶圈

由于 \(u\) 缺少颜色 \(\alpha\) 但可能连接颜色 \(\beta\) 的边，故 \(u\) 在 \(H_{\alpha\beta}\) 中度数为 1，是某条路径的端点，记该路径为 \(P_u\)

若路径 \(P_u\) 不到达 \(v\)，则 \(u\) 和 \(v\) 在 \(H_{\alpha\beta}\) 的不同连通分支中，此时可以交换 \(P_u\) 上所有边的颜色（\(\alpha \leftrightarrow \beta\)），交换后，\(u\) 缺少颜色 \(\beta\)，此时回到情形 \(\alpha = \beta\)，用 \(\beta\) 给 \(e\) 着色即可

若路径 \(P_u\) 到达 \(v\)，则存在一条 \(u\) 到 \(v\) 的路，其颜色交替为 \(\beta, \alpha, \beta, \dots\)

由于 \(v\) 缺少颜色 \(\beta\)，进入 \(v\) 的边颜色必为 \(\alpha\)

这意味着路径长度为偶数。若加上边 \(e=(u,v)\)，则形成一个长度为奇数的圈

这与二分图不含奇圈的性质矛盾

因此路径 \(P_u\) 不可能到达 \(v\)，故总能找到合法的着色方案

综上，\(\chi'(G) \le \Delta(G)\)

定理 7.5.2 Vizing 定理

对任意简单图 \(G\) 有 \(\Delta \le \chi' \le \Delta+1\) 即 \(\chi'=\Delta\) 或 \(\chi'=\Delta+1\)

证明： 点击查看证明

只需证明 \(\chi'(G) \le \Delta(G) + 1\)

令 \(k = \Delta(G) + 1\)，对 \(G\) 的边数 \(|E|=m\) 进行归纳

当 \(m=1\) 时显然成立，假设对于 \(m-1\) 条边的简单图结论成立

设 \(G\) 有 \(m\) 条边，取 \(e_0 = xy_0 \in E(G)\)

根据归纳假设，\(G - e_0\) 存在 \(k\)-边着色，由于每个顶点的度数 \(\le \Delta < k\)，对于任意顶点 \(v\)，至少存在一种颜色未在 \(v\) 处使用，记为 \(c(v)\)

构造一个以 \(x\) 为中心的一系列边：\(xy_0, xy_1, \dots, xy_s\)

满足对于 \(0 \le i < s\)，边 \(xy_{i+1}\) 的颜色是 \(y_i\) 处缺失的颜色

选取一个极大化的 \(s\)，使得 \(c(y_s)\) 满足以下两种情况之一：

1. \(c(y_s)\) 在 \(x\) 处也缺失。
2. \(c(y_s)\) 在 \(x\) 处已被使用，且被某条边 \(xy_k\) 使用（其中 \(1 \le k < s\)）

令 \(\alpha = c(y_s)\)（\(y_s\) 处缺失的颜色）， \(\beta = c(x)\)（\(x\) 处缺失的颜色）

情况1：若 \(\alpha = \beta\) 或 \(\alpha \in c(x)\)，即 \(\alpha\) 在 \(x\) 处也缺失

将边 \(xy_0\) 染成 \(color(xy_1)\)，边 \(xy_1\) 染成 \(color(xy_2)\)，…，边 \(xy_{s-1}\) 染成 \(color(xy_s)\)

此时边 \(xy_s\) 变为未着色，但由于 \(x\) 和 \(y_s\) 都缺少颜色 \(\alpha\)，直接将 \(xy_s\) 染为 \(\alpha\) 即可

情况2：若 \(\alpha\) 在 \(x\) 处已被使用

由 \(s\) 的极大性，必存在某个 \(k\) (\(1 \le k < s\)) 使得 \(color(xy_k) = \alpha\)

又因为定义 \(color(xy_k) = c(y_{k-1})\)，所以顶点 \(y_{k-1}\) 也缺失颜色 \(\alpha\)

考虑仅由颜色 \(\alpha\) 和 \(\beta\) 构成的子图 \(H_{\alpha\beta}\)，顶点度数至多为 2，其连通分量为路径或偶圈

\(x\) 连接了 \(\alpha\) 边 (\(xy_k\))，但缺失 \(\beta\)，故度数为 1，\(y_s\) 缺失 \(\alpha\)，可能连接 \(\beta\) 边，故度数 \(\le 1\)，\(y_{k-1}\) 缺失 \(\alpha\)，可能连接 \(\beta\) 边，故度数 \(\le 1\)

这三个点不可能属于同一个连通路径

1. 若 \(x\) 和 \(y_s\) 不在 \(H_{\alpha\beta}\) 的同一个连通分量

   在包含 \(y_s\) 的连通分量中交换颜色 \(\alpha\) 和 \(\beta\)，交换后，\(y_s\) 原本缺失 \(\alpha\)，现在变为缺失 \(\beta\)，此时 \(y_s\) 和 \(x\) 都缺失 \(\beta\)。我们对序列 \(xy_0, \dots, xy_s\) 进行左移操作，最后将 \(xy_s\) 染成 \(\beta\)

2. 若 \(x\) 和 \(y_s\) 在同一个连通分量中

   则\(x\) 和 \(y_{k-1}\) 必然不在同一个连通分量中，在包含 \(y_{k-1}\) 的连通分量中交换颜色 \(\alpha\) 和 \(\beta\)，交换后，\(y_{k-1}\) 原本缺失 \(\alpha\)，现在变为缺失 \(\beta\)

   此时 \(y_{k-1}\) 和 \(x\) 都缺失 \(\beta\)。我们仅对部分扇形 \(xy_0, \dots, xy_{k-1}\) 左移染色（2颜色变为1颜色，3颜色变为2颜色，以此类推），最后将 \(xy_{k-1}\) 染成 \(\beta\)

综上，无论哪种情况，都能成功为 \(e_0\) 着色且不破坏其他边的合法性

故 \(\chi'(G) \le \Delta(G) + 1\) 得证

定义 7.6 面着色

把 \(k\) 中颜色对图 \(G\) 的任意相邻两个面着不同颜色，则称为 \(G\) 的一个 \(k\)-着色，着色数 \(\chi^*(G)\) 是能给 \(G\) 着色的最小颜色数，若 \(\chi^*(G)=k\) 则称 \(G\) 是 \(k\) 面色的

根据对偶图的定义可知，面着色问题等价于对偶图的顶点着色问题，因此有 \(\chi^*(G)=\chi(G^*)\)

定理 7.6.1

下面三个叙述等价

• 每个平面图都是 \(4\) 顶点可着色的
• 每个平图都是 \(4\) 面可着色的
• 每个简单 \(2\) 边连通 \(3\) 正则平面图都是 \(3\) 边可着色的

定理 7.6.2

任何图都是 \(5\) 可着色的