五色定理是图论中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比四色定理弱，也比四色定理更容易证明。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的点。

如果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-着色。

如果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-着色。

参考资料
*