查看“︁五色定理”︁的源代码

{{expand english|time=2018-11-17T08:54:45+00:00}}
{{refimprove|time=2013-03-22T05:13:35+00:00}}
'''五色定理'''是[[图论]]中的一个结论：将一个平面分成若干区域，给这些区域染色，且保证任意相邻区域没有相同颜色，那么所需颜色不超过五种。五色定理比[[四色定理]]弱，也比四色定理更容易证明。1879年，{{Link-en|阿尔弗雷德·肯普|Alfred Kempe|阿尔弗雷德·布雷·肯普}}给出了四色定理的一个证明，当时为人所接受，但11年后，[[彭西·希伍德|珀西·约翰·希伍德]]却发现了肯普的证明中存在错误，他把肯普的证明加以修改，得到了五色定理。

==证明==
以下是对五色定理的证明<ref>{{Citation|last1=Harris|first1=John|last2=Hirst|first2=Jeffry L.|last3=Mossinghoff|first3=Michael|title=Combinatorics and Graph Theory|year=2008|pages=98–99|publisher=Springer-Verlag New York|series=Undergraduate Texts in Mathematics|isbn=978-0-387-79711-3|doi=10.1007/978-0-387-79711-3}}</ref>。

给定<math>n</math>阶平面图<math>G</math>，我们对<math>G</math>的阶数进行归纳证明。

当<math>n\leq 5</math>时，正确性显然。

假设<math>n\geq 6</math>且对于任意的<math>n-1</math>阶平面图该结论成立。因为<math>G</math>是平面图，那么存在点<math>v\in V(G)</math>，满足<math>d(v)\leq 5</math>（通过[[欧拉示性数|欧拉公式]]可知对任意平面图<math>G</math>，<math>\delta(G)\leq 5</math>）。

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

我们希望通过调整<math>G'</math>的着色方式，使得<math>v</math>有色可染。考虑<math>G'</math>中所有颜色为<math>1</math>或<math>3</math>的点。

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

综上所述，<math>G</math>能进行5-着色。

==参考资料==
*{{Citation|last=Heawood |first=P. J. |title=Map-Colour Theorems |periodical= Quarterly Journal of Mathematics, Oxford |volume= 24 |year = 1890 |pages = 332–338 |authorlink=}}

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