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

证明

编辑

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

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

 时,正确性显然。

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

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

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

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

综上所述, 能进行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