五色定理

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

证明

以下是对五色定理的证明^[1]。

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

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

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

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

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

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

综上所述，${\displaystyle G}$ 能进行5-着色。

参考资料

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

1. Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael, Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag New York: 98–99, 2008, ISBN 978-0-387-79711-3, doi:10.1007/978-0-387-79711-3