五色定理

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

证明

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

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

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

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

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

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

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

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

参考资料

• Template:Citation