最后更新: 2025-01-22 09:38 ● 参与者查看: 24 次纠错分享参与项目词条搜索

五色定理

定理 9.10 任何平面图 $G$ 是 5－可着色的。
证明：不妨设 $G$ 是平面简单图。对 $G$ 的顶点数采用数学归纳法。当 $n \leqslant 5$ 时结论成立。假设 $n-1$ 个顶点的所有平面简单图 $G$ 是 5－可着色的。考虑 $n$ 个顶点的平面简单图 $G$ ，由定理 9．2，在 $G$ 中存在顶点 $v_0$ ，使 $d \left(v_0\right) \leqslant 5$ 。由归纳假设，$G-v_0$ 是 5 －可着色的，在给定 $G-v_0$ 的一种着色之后，将 $v_0$ 及其关联边加回到原图中，得到 $G$ ，分两种情况。
（1）如果 $d\left(v_0\right)<5$ ，则 $v_0$ 的相邻点已着上的颜色小于等于 4 种，所以 $v_0$ 可以着另一种颜色，使 G 是 5 －可着色的。
（2）如果 $d\left(v_0\right)=5$ ，则将 $v_0$ 的相邻点依次记为 $v_1, v_2, \cdots, v_5$ ，并且对应的 $v_i$ 点着第 $i$ 色。
设 $H_{13}$ 为 $G-v_0$ 的一个子图，它是由色 1 和色 3 的顶点集导出的子图。如果 $v_1$ 和 $v_3$ 属于 $H_{13}$ 的不同分支，将 $v_1$ 所在分支中着色 1 的顶点和着色 3 的顶点进行颜色对换，这时 $v_1$ 着色 3 ，并不影响 $G-v_0$ 的正常着色。然后在 $v_0$ 着色 1 ，因此 $G$ 是 5 －可着色的。

如果 $v_1$ 和 $v_3$ 属于 $H_{13}$ 的同一分支，则在 $G$ 中存在一条从 $v_1$ 到 $v_3$ 的路，那么这条路与 $\left(v_1, v_0\right.$ ， $\left.v_3\right)$ 一起构成一条回路，并且该回路或者将 $v_2$ 围在里面，或者把 $v_4$ 和 $v_5$ 围在它里面。因为 $G$ 是平面图，在任何一种情况下，都不存在连接 $v_2$ 和 $v_4$ 的一条路。现在设 $H_{24}$ 为 $G-v_0$ 的另一个子图，它是由着色 2 和色 4 的顶点集导出的子图，则 $v_2$ 和 $v_4$ 属于 $H_{24}$ 的不同分支，所以在 $v_2$ 所在分支中将着色 2 的顶点和着色 4 的顶点进行颜色对换，$v_2$ 着色 4 ，这样导出了 $G-v_0$ 的另一种正常着色。然后在 $v_0$ 着色 2 ，同样得到 $G$ 是 5 －可着色的。

二色定理
定理 9.11 地图 $G$ 是2－面可着色的当且仅当它是一个欧拉图。
证明：$\Rightarrow$ 设地图 $G$ 是2－面可着色的，对于 $G$ 中任意一个顶点 $v$ ，围绕顶点 $v$ 的面必为偶数个，于是可推出 $v$ 是偶顶点，由定理 8.14 ，可知 $G$ 是欧拉图。
$\Leftarrow$ 设 $G$ 是欧拉图，则由定理 8.16 可知 $G$ 可分解成若干个边不相重的回路的并。对图的回路数 $p$ 采用数学归纳法。当 $p=1$ 时，$G$ 是 2 －面可着色的。假设回路数为 $p-1$ 的地图 $G$ 是 2 －面可着色的。对于由 $p$ 条回路构成的地图 $G$ ，由于 $G$ 的每个顶点都是偶顶点，在 $G$ 中删去一条回路，得到图 $G^{\prime}, G^{\prime}$ 的每个顶点的度数也是偶数。根据归纳假设，$G^{\prime}$ 是 2 －面可着色的。再把删去的回路加回到 $G^{\prime \prime}$ 中得到 $G$ ，并且使这条回路外的所有面的颜色保持不变，而回路所围的各面已着两种颜色，将这两种颜色对换，得到 $G$ 是 2－面可着色的。

上一篇：平面图的着色

下一篇：边的着色

本文对您是否有用？有用 (0) 无用 (0)