为给网友学习四色问题,探究证明方法创造条件.本人从图论书上节选五色定理的证明,供参考.1840年麦比乌斯首先提出对任意的地图(平面图),四种颜色是足够的,但未能加以证明,这就是著名的四色定理.这个问题有各式各样的表现形式,比如说作平面图G对偶图G',可以证明G'也是平面图,G的面的涂色问题就变成G'的顶点的涂色问题,四色定理就等价于证明平面图G'的色数</=4.

虽然四色定理是很难证的,五色定理的证明却很容易,我们现在就可以证明它.

定理三    平面图的色数</=5 .

证明  对平面图G的顶点个数N进行归纳.N=5时命题显然成立.假设对顶点个数为N-1的平面图命题成立.

因平面图G有一个顶点V,满足DEGv</=5,将V及与V相邻的边去掉后得图G',由归纳假设,G'的色数</=5,设G'的顶点已经涂上了五种颜色a'/a"/a'"/a""/a'"",每两个相邻的顶点颜色不同.

如果degv<5,将V涂上与相邻顶点(至多四个)均不相同的那一种颜色,就完成了图G的涂色.

如果degv=5(图1),即V有五个相邻的顶点V'/V"/V'"/V""/V'"",这时又有两种情况:

             V'

             |

             |

    V'""-----V-------V"

           /   \

          /     \

         V""      V'"    图 1.

1 .这五个顶点的颜色不全不同.这可以和上面一样地解决.

2 .这五个顶点的颜色互不相同,不妨设它们分别为a'/a"/a'"/a""/a'"".

考虑G'中由a'/a"这两种颜色的顶点及它们之间的边所组成的图G~(a'a").如果G'(a'a")中有一个连通分支只含V'不含V",我们将这个连通分支中a',a"这两种颜色对调,于是V'成为a"色,从而V可涂上颜色a',命题成立.因此如果定理三不成立,那么V'与V"一定在G'(a'a")的同一个连通分支中,即V'与V"之间有一条链.同样,任意两个Vi(1</=i</=5)之间有一条链.把链上其它顶点忽略掉,得到一个以V'/V"/V'"/V""/V'""为顶点的子图K/5,但K/5不是平面图,矛盾.所以定理三是成立的.

  此文节选自"趣味的图论问题"(上海教育出版社)第57----58页.