五色定理

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

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

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

当时，正确性显然。

假设且对于任意的阶平面图该结论成立。因为是平面图，那么存在点，满足（通过欧拉公式可知对任意平面图，）。

考虑图。因为，由归纳假设知能进行5-着色。假设使用五种颜色着色。考虑的相邻点，如果在中它们用了不到五种颜色着色，那么我们从剩下的颜色中选一个为着色，就得到了的一个5-着色方式。如果在中它们用上了所有五种颜色，这就意味着有且仅有5个相邻点（），从顺时针方向我们依次称它们为，不失一般性，假设的颜色为。

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

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

訂閱不錄菜鳥，能进行5-着色。

参考资料

Category:图染色
Category:数学定理
Category:组合数学