四色猜想的证明

教师之友网

四色猜想的证明

图论中的一个著名的问题——四色猜想，是一个直到现在都还没有得到理论解决的问题，它可以叙述为：对任意一个平面地图着色，只需要四种颜色，就能让任两个相邻的面着上不同的颜色。1976年，美国阿普尔、恩肯和考齐等三位科学家宣称他们借助于计算机，耗时1200个小时，做了近百亿次判断后，证明了四色猜想，这引起了许多争论，这些近百亿次的判断，难道真的是证明吗？而我更是认为：一个真正的数学证明，应该是一首诗，而它纯属一本电话簿！                                      我们容易知道，证明四色猜想，完全可以把它转化为证明一个平面地图中至多有四个平面相邻的等价命题。

证明四色猜想需要有下面的概念：                                  定义（1）：着色有（无）效边：如G的一条边e,若对G是n—着色的问题与对(G-e)是n—着色的问题等价，则称e为G的着色无效边；反之，则称e是G的着色有效边，如图中的{u6,u5},{u2,u4},{u8,u9},都是该图的着色无效边，其他边都是着色有效边。根据着色无效边的定义，去掉图G的所有或几条着色无效边后，该图的着色不变，我们可以得到下面的性质：            性质（1）：一条边e是图的着色无效边当且仅当在G中没有包含e的回路。 证明：由于面着色问题是关于面的问题，对着色问题有无影响，就是看该过程有无改变图的面数，所以，对e是G的着色无效边的意义就是该边的存在与否不影响图的面数，显然，如果边e参与形成了回路，去掉e就会使图的面数增加一个，反之，若e没有参与形成回路，则它不是两个面的公共边，去掉它就不会影响面数，该性质成立。

我们再来看下面的一个问题，看对偶图的定义：

“在图G的每一个面Si(i=1、2……、f)中放置一个顶点ui＊,如果Si和Sj相邻，则用边（ui＊,uj＊）连接ui＊和uj＊，使它与面Si和Sj的公共边只相交一次，此时称（ui＊,uj＊）与所相交的边为对应边，且（ui＊,uj＊）与G的其他边界无交点，这样得到的图G＊称为图G的对偶图。”

这个定义会造成下面一个不必要的麻烦，两个面可能有几条公共边，这样得到对偶图中，连接两个相邻面中的两个点ui＊和uj＊就有很多条，而要显示这两个点是相邻的（即原图中两个面上相邻的）只需要一条线即可，为了解决这个麻烦，我们有下面的定义：

定义（2）：着色有（无）效点：如果u∈V(G),称以u作为着色有效边的次数之和为u的有效度数，记为dG,在不引起混淆的情况下，可记为d,若d[u]﹤3，则称u为G的着色无效点，否则称e为G的着色有效点，如图中的u2，u5，u4，u6，u7，u8，u9皆为着色无效点，事实上，着色无效点的规定，就等于是让两个面的公共边合为几条不相邻的边，而且，悬挂点、独立点均被视为着色无效点，我们还有下面的定义：

定义（3）：删去G中的所有着色无效边、着色无效点所得到的图G1的对偶图G1＊，若对G1＊中相邻的两点只保留一条边，其余的边抹掉，这样所得到的图称为图G的最简对偶图，记为[G＊]。

我们有下面的性质：

性质（2）：平面地图G是n-可着色（指面着色！）的说法与图[G＊]是n-可着色（指点着色！）的说法是等价的。

证明：若G1＊是n-可着色的，由于[G＊]中，G1＊中相邻的顶点在[G＊]中仍然是相邻的，若G1＊是n-可着色的就意味着[G＊]是n-可着色的，反之也是成立的，即[G＊]是n-可着色的与G1＊是n-可着色的说法是等价的，而G1＊是n-可着色与G1是n-可着色的说法等价，由前面的分析知道，G1是n-可着色与G是n-可着色的说法是等价的，故G是n-可着色的说法等价于[G＊]是n-可着色的。

由对偶图的定义，我们有下面的性质：

性质（3）：将图H定义为H中的任意两个面都是相邻的,若将一个图的对偶图画成其中的每两条边除了端点以外不相交（由于任意两个相邻的点都有一条对应边，所以这是很容易办到的），则图H的最简对偶图[H＊]是一个完全可平面图。

这个性质由对偶图的定义就可以很容易地证明。

再来看下面一个性质：

性质（4）：对n阶完全图Kn,当且仅当n≧5时,Kn是不可平面的。

证明：因K5是不可平面的，对Kn（n≧5）的一个5阶导出子图也是完全图，这个子图是不可平面的，则整个图Kn也是不可平面的，又由于K2、K3、K4都是可平面的，故原性质成立。

若用∣vH＊∣表示[H＊]的顶点数，那么性质（3）、（4）说明了∣vH＊∣≦4，既是说明了[H＊]是4—可着色的，又由前面的讨论知，H是n-可着色的等价于[H＊]是n-可着色的，故H是4-可着色的。由H的定义，知道这既是说明了一个平面图中至多有四个面相邻，这是四色猜想的等价命题，四色猜想得证。

当然我们由四色猜想可以得到，在任一个平面地图中：

（1）最多有三条边两两相关（可以把它叫做一维空间的三色定理）；

（2）最多有四个顶点两两邻接。

现在我们来总结一下,造成四色现象的原因是什么?是由于在一个平面地图中, 最多有四个顶点两两邻接,而造成这样一个现象的原因又在于: 在任一个平面地图中,最多有三条边两两相关,所以,四色现象是由一维空间的三色现象造成的。