五色定理

维基百科,自由的百科全书

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