五色定理

五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比四色定理弱，也比四色定理更容易证明。1879年，阿尔弗雷德·布雷·肯普给出了四色定理的一个证明，当时为人所接受，但11年后，珀西·约翰·希伍德却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。

证明

以下是对五色定理的证明。

给定$n$阶平面图$G$，我们对$G$的阶数进行归纳证明。

当$n\leq 5$时，正确性显然。

假设$n\geq 6$且对于任意的$n-1$阶平面图该结论成立。因为$G$是平面图，那么存在点$v\in V(G)$，满足$d(v)\leq 5$（通过欧拉公式可知对任意平面图$G$，$\delta (G)\leq 5$）。

考虑图$G':=G-v$。因为$|G'|=n-1$，由归纳假设知$G'$能进行5-着色。假设$G'$使用$1,2,3,4,5$五种颜色着色。考虑$v$的相邻点，如果在$G'$中它们用了不到五种颜色着色，那么我们从剩下的颜色中选一个为$v$着色，就得到了$G$的一个5-着色方式。如果在$G'$中它们用上了所有五种颜色，这就意味着$v$有且仅有5个相邻点（$d(v)\leq 5$），从顺时针方向我们依次称它们为$w_{1},w_{2},w_{3},w_{4},w_{5}$，不失一般性，假设$w_{i}$的颜色为$i$。

我们希望通过调整$G'$的着色方式，使得$v$有色可染。考虑$G'$中所有颜色为$1$或$3$的点。

1. 如果$G'$中不存在这样一条连接$w_{1}$与$w_{3}$的路径，路径上所有点的颜色均为$1$或$3$。定义$H\subseteq G'$是满足以下条件的所有路径的并集：以$w_{1}$为起点且路径上所有点的颜色均为$1$或$3$。注意到$(w_{3}\cup N(w_{3}))\cap V(H)=\emptyset$。此时我们可以将$H$中所有点的颜色互换：把$3$换成$1$，把$1$换成$3$。交换之后也是$G'$的一个5-着色方式。此时$w_{1}$的颜色变成了$3$，我们将$v$染为$1$。因此，$G$能进行5-着色。
2. 如果$G'$中存在这样一条连接$w_{1}$与$w_{3}$的路径，路径上所有点的颜色均为$1$或$3$，我们称之为$P$。注意到$P$与$v$共同形成了一个环，这个环要么把$w_{2}$要么把$w_{4}$圈在里面。此时我们发现，不存在这样一条连接$w_{2}$与$w_{4}$的路径，路径上所有点的颜色均为$2$或$4$。我们只需按照情况1中的方式调整颜色即可。因此，$G$能进行5-着色。

综上所述，$G$能进行5-着色。

参考资料

• Heawood, P. J., Map-Colour Theorems, Quarterly Journal of Mathematics, Oxford 24, 1890, 24: 332–338