浅析四色猜想的证明

浅析四色猜想的证明

学生姓名：杨彩娟 指导老师：冯源

摘 要 四色定理是世界三大数学难题之一，许多数学家多年来都热衷于它的证明，力求寻找更好

的非计算机证明方法，而四色猜想的讨论和证明也大大推动了图论的发展。

关键词： 图论； 四色猜想； 四色证明； 可约化构形

引言：

在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻国家的颜色不同。这样的着色效果能使每一个国家 能清楚地显示出来。但要证明这个结论却是一个著名的世界难题，最终借助计算机才得以解决，之后诸多数学学者都在寻找其严格数学证明方法。

图论是当今数学中较为发达的一门学科，它被广泛应用于道路交通、通讯工程、经营管理等诸多领域，如今图论还衍生出网络理论这种新生事物。世界上许多事物以及它们之间的联系都可以用图形来直观表示，这时人们所研究的对象往往用结点表示事物，用边表示它们之间的联系。这种由结点和边构成的图形就是图论里研究的平面图，而其与平面几何中的图不相同,这里只关心图中有多少个点,点与点之间有无连线,至于连线的方式是直线还是曲线,点与点的相对位置如何,都是无关紧要的。总之,这里所讲的图是反映对象之间关系的一种工具。在图的理论研究和实际中,图的平面化问题具有非常重要的意义，而四色猜想的讨论大大推动了图论的发展。

地图是我们生活中不可或缺的一项实用工具。在绘制地图时相邻区域最好涂上不同的颜色以示区别，而这样的结果只会使地图看起来花花绿绿，然而实际上只需要四种颜色就能保证相邻两个地区颜色不重复。这就是著名的四色猜想（也称作四色问题）。

英国青年弗朗西斯·葛斯瑞于1852年在给一张英国地图着色时发现了四色问题，但之后很多人都无法解释这个问题。直到英国数学家凯莱于1878年在皇家学会上正式提出并在《皇家地理学会会报》上发表，这才使得四色问题得到广泛关注。随后各国数学中心和数学杂志都收到大量的证明，正像许多这种提法简单而证明极为困难的大猜想一样，许多的证明完全是错的。到了1890年，剑桥大学三一学院的毕业生肯普在《美国数学杂志》上发表的四色猜想的证明被数学大师希伍德指出有漏洞，尽管四色猜想没有得到证明，但肯普和希伍德两位数学大师对于后来图论的发展做出了决定性的贡献。迄今为止，四色猜想仍然是电脑证明数学难题绝无仅有的例子，但它昭示了计算机证明时代的到来，它也可能成为数学上一系列新思维的起点，四色猜想同时也是第一个应用计算机辅助证明的大定理，但主导整个证明过程的仍然是数学家。四色猜想看起来是一个带有数学游戏性质的孤立问题，但它创造出图论许多新的分支。证明四色定理也需在概念上下功夫，特别是需要寻找可约化的构形，即把复杂的事物变成简单的对象，把区域多的问题简化为区域少的情形。那么四色问题可以做这样的化简：一个区域不妨看成一个点，任何两个区域或者相邻或者不相邻。如果代表两个区域的点相邻，那么我们就在两点之间连上一条线，否则就不连线。这样的结构就称作图。这时四色问题也就变成图的顶点着色问题，也就是两顶点如果有线相连，就必须涂上不同的颜色。任意一个图，它可能的最小着色数称为它的色数。20世纪60年代，证明四色猜想的构型大约有8000到10000个，这在当时用计算机是办不到的。后来阿沛尔与哈肯利用计算机进行搜索，发现构型不到

2000个，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿次判断，终于完成了四色定理的证明。这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。它不仅解决了一个历时100多年的难题，而且有可能成为数学史上一系列新思维的起点。不过也有不少数学家并不满足于计算机取得的成就，他们还在寻找一种简捷明快的书面证明方法，就是直到今天，仍有很多的数学学者在寻找证明四色问题的更好的方法，这其中不泛有诸多正确的证明，而这些证明也再次肯定了四色猜想。从而四色问题也成了历史上经典的定理之一，即四色定理.

下面就列举两个四色猜想的相对严格的非计算机证明方法，并作简要的分析：

证明方法一：

其证明的理论体系如下：

公理1：任何直达的（直接相连接的）两点，必须采用不相同的颜色。（注：本文均采用“点着色”的方法）

公理 2：任何不能直达的两点可以采用相同的颜色着色。

公理3：在“平面”或“球面”上任何一个“封闭圈”（指若干条首尾相连的“线”所构成的图形）都可将“平面”或“球面”“分断隔离”成为不能直达的两部份，即这一部份内（即这个“圈”内）的点必须经过“封闭圈”（以后简称为“圈”）上的点才能到达另一部份内（即这个“圈”外）的点（在着色问题中，“线”与“线”之间是不能交叉的。因为如果“线”与“线”之间交叉则它们显然不能处于同一“平面”或“球面”上了。

公理 4：在“环面”（形如普通的救生圈）上有些“封闭圈”是不能起到“分断隔离”的作用的。即“圈”一侧的“点”可以不必非要通过“圈”上的点就可以到达“圈”的另一侧的点。（这种“环面”实际上是“七可着色”的，但本文不加以讨论）

定理 1：每一个没有三角形的可平面图是3可着色的（即X（G）≤3）

定理2：一个图是双可着色的，当且仅当它没有“奇圈”。定理3：在“平面”或“球面”上的完全图K4的着色数为4。

定义1：一个“奇圈”或“偶圈”内有一些点，则这些点叫作这个圈的“圈内点”。这个“圈”叫作这些点的“点外圈”。

定义 2：一个“奇圈”或“偶圈”外有一些点，则这些点叫作这个圈的“圈外点”。

实际上“内”与“外”都是相对而言的。特别是在“球面”上更为明显。

定义 3：一个“奇圈”或“偶圈”上有一些点，则这些点叫作这个圈的“圈上点”。

定义 4：如果一个圈内仅有一个点，则这个“圈”称为这个点的“最小圈”。

定义5：如果去掉了某一个“着色点”之后并不改变原图的“着色数”，那么称这点为“着色可省略点”。

定理 3：如果一个图中仅有一个“圈”及圈内仅有一个点，且这点与“圈上点”都分别相连则这个图的着色数：X（G）≤4。

定理 4：在平面图中增加一条连接原图中尚未连接的两点之间的连线，则新图的着色数不小于原图的着色数

定理 5：一个仅有“圈上点”（即既没有“圈内点”又没有“圈外点”）的三角剖分图是3可着色的。即X（G）=3

定理 6推论：一个仅有“圈上点”的图的着色数有X（G）≤3

定理7：对于任何平面图有着色数：X（G）≤5（此定理在本文证明四色定理时可以不利用，但若利用此定理则在叙述本文的证明时会更为方便些，此定理在各图论书中均有证明）

定理8: 任何一个封闭的三维空间,只要它里面所有的封闭曲线都可以收缩成一个点,这个空间

就一定是一个三维圆球。（庞加莱定理）

定理8的推论：在“球面”上挖一个“洞”就变成了拓扑学意义上的“平面”了。在“球面”上挖二个“洞”就变成了拓扑学意义上的“圆柱侧面”了。在“球面”上不论挖多少个“洞”都不会改变原来“球面”上的“着色数”。

证明：将有限“平面”的“四周”在空间向外收缩为一点，或将“圆柱”的上下底面都收缩

为一个点就也成了三维圆球的球面。（庞加莱定理）所以“平面”“圆柱侧面”等曲面在拓扑意义上就是“球面”

四色定理的证明

四色定理：在球面或平面上对于任何平面图有X（G）≤4

证明：（反证法）

假设四色定理不能成立，即存在某平面图是必须用5种或5种以上的颜色来着色。即有X（G）≥5，不失一般性，可作一个任意复杂的图，如图（3）其中的实线部分表示全图的一个很小的局部图，虚线部分表示省略了的大部分图形。其复杂程度可以任意构筑和想象，但必须是“有限图”而不应该是“无限图”。

图（3）

然后对此图作以下几个步骤的处理与分析：

第一步：在保持原图的所有点与连线的基础下，再将原图中尚未相连但却能够相连的各点两两

之间尽可能多地连接起来，（应注意不再增加新的着色点，而仅仅增加连线）直至成为“三角剖分图”为止。由前面定理5可知这样处理之后新图的着色数不会比原图减少，这一步称之为“添线”。

第二步：任取图内某一个“圈内点”及围绕这点的“最小圈”进行分析。例如我们取的这个

“圈内点”为V0，且在“添线”时我们已经连接了V0与V4及V0与V5，并且还连接了V3与V7及V4 与V8„已经把原图变成了一个“三角剖分图”这时V0的“最小圈”就是V1—V2—V3—V4—V5—V1。 对于这个“局部图形”进行着色调整与分析。根据定理4，我们可以把V0的最小的“点外圈”安排

第二、第三种颜色进行着色。把V0安排为第四种颜色进行着色。然后再给所有“圈外的点”都着上

颜色，由假设可知其“着色数”X（G）≧5，但由前面的“公理2”和“公理3”可知“圈内点”与 “圈外点”不可能直达，故可以把V0这点的着色由原来安排的第四种颜色调整为第五种颜色，再由

定义5可知若这时把V0这点连同V0直接相连的所有连线都去掉。这样做也并不会减少原图的“着色

数”。（因为V0这点是被它的四周的“最小圈”阻断隔绝在圈内的，它与“圈外 点”的着色是无关

的。如果说这样做减少了原图的着色数，例如“着色数”从五减少为四，则说明原图的“着色数” 本来就应该是四。）这一步称之为“去点”与“去线”。（这时的V0点是“着色可省略点”，而V0点既

然已经去掉，则与它直接相连的各条线，也就自然没有存在的必要了。因为本文采用的是点着色的 方法。）

第三步：反复对图中其它各“圈内点”作第一步的“添线”或第二步的“去点”与“去线”，（可交替或不交替地使用）直至对图中的任何一点来说都再也没有“圈内点”可去了为止。最终使它成为一个“三角剖分图”。因为“点”在一个又一个地减少，且“圈内点”与“圈外点”是相对而言的。所以最终的结果只能得到只有一个“圈”且圈内只有一个点的图（这时“圈内点”与“圈上点”相连）或一个只有“圈上点”的“三角剖分图”。但这时的“着色数”X（G）≤4。这显然与开始的假设X（G）≥5相矛盾，所以一开始的假设X（G）≥5是错误的。故在“球面”或“平面”上的着色数有X（G）≤4成立。证明完。

证明方法二：

任意平面图G=都是5可着色的。但是后来在平面图上经过多次试验，没有找到一种平面图一定要用5种颜色的。在一百多年前，有人猜测只要用4中颜色就够了，这就是世界上著名的4色猜测问题。这个猜测一经提出，迷住了许多数学家，但是谁都无法用数学的方法证明它。直到1976年，阿沛尔和哈肯两人宣布了四色理论的证明方法。他们用大型电子计算机分析了2000多种图包括几百万种情况，花了大量的机器时间，终于证明了这个问题，从而解决了一百多年来引人关注的难题。显然这不是纯理论上的严格证明，我们虽然有理由相信计算机不会出错，但是又该怎么证明计算机没有出错呢？以下运用方程组计算连通平面图的着色数，对连通平面图的面色数作出初步的判定。

基本性质

定义1如果图G能以这样的方式画在曲面S上，即除顶点处外无边相交，则称G可嵌入曲面S.若G可嵌入平面，则称G是可平面图或平面图。画出的无边相交的图称为G的平面嵌入。无平面嵌入的图称为非平面图

定义2设v是图G的一个顶点，将顶点v变换成一个面r，原来和顶点v相接的边变换为与面r相接且各边互不相交，称为顶点v的扩张；而将面r变换成一个顶点v，原来和面r相接的边变换后相交于顶点v，称为面r的收缩。

引理1 顶点的扩张或面的收缩不影响图的平面性，也不改变非变换顶点或面的相互位置。

证： 显然，由定义1可知，除发生变化的点或面外，原图中其它的点和面的位置在新图中都没有发生改变。

定义3 对平面图G的每个面涂上一种颜色，使相邻的面涂不同的颜色，称为对G的一种面着色，若能用k种颜色给G的面着色，就称对G的面进行了k着色，或称G是k-面可着色的。若G是k-面可着色的，但不是(k-1)-面可着色的，就称G的面色数为k，记作χ*(G)=k

定义4若平面图G有χ*(G)=k，且对图G的面进行了k着色，则称对图G正确着色。

定义5 设已正确着色平面图G有χ(G)=k，那么对任意的一种颜色R，若存在一个色块D与k-1种颜色相邻，则D称为基本色块。

定义6 设已正确着色图平面图G仅有k个不同色色块两两相邻，称图G为基本k-色图。

引理2 若连通平面图G有χ*(G)=k，则存在基本k-色图。

*

证 设连通平面图G已经正确着色且有χ*(G)=k，那么对于任意的颜色R存在基本色块。设对于颜色R不存在基本色块，即对于颜色R的任意一个色块D其相邻色数都小于k-1种，那么颜色R就不是必需的，色块D至少与一种颜色不相邻，用与色块D不相邻的颜色替换色块D的颜色R。当所有着颜色R的色块都被替换后，显然有χ*

(G)

*k-1，矛盾既然任意颜色基本色块存在，那么由χ(G)=k知，图G至少存在k个不同颜色的基本色块，保留颜色R的一个基本色块，对其它的R色块

**做面的收缩，由引理1可以得到一个已正确着色的新图G*，图G*只有一个R色块且χ*(G*)=k。对其他颜色的色块做如上变换，最后得到仅有k个不同色色块两两相邻的连通平面图，且χ(G)=k。所

以若连通平面图G有χ(G)=k，则存在基本k-色图。

定理 球面上任意的连通平面图都有χ*

(G)

证 设χ*(G)=k，由定理3，有k=1、k=2或

4 *

，得

，

(1)

，又

，得

，代人(1)，

χ*

(G)4 毕。

所以，对球面上任意的连通平面图各个面着色，使得相邻的面有不同的颜色，所用的颜色可以不多于4种，即球面上的平面图都是4-面可着色的。四色定理得证。

可见在证明四色猜想上数学家想了很多的方法，两种证明方法的共同之处都建立了可约化构型，第一种证明方法中整个证明过程主要是围绕着“全图”中的“局部图”的“圈”及“圈内点”，“圈外点”进行分析与处理的。“三角剖分”图中的“三角”实质上就是由三点构成的“圈”。如果图中出现由大于三点所构成的“圈”，则可以通过“添线”的方法使其成为“三角剖分图”然后再进行分析与处理。如果图中出现由二点构成的“圈”或出现由一点构成的“圈”（例如出现一个区域包围了另一个区域的情况），前文中虽然没有提及，但对于它的分析与处理方法与由三点所构成的“圈”可完全相同。而且其证明过程中利用了如下特点：在“球面”或“平面”上在着色问题中的最重要

的特点就是任何“圈”在“球面”或“平面”上的“阻断”作用。同样“圈”在所有“简单多面体”上也有这样的“阻断”作用。但在“非简单多面体”上有些“圈”就不再具有这种“阻断”作用，本文正是利用了这一特点证明了“四色定理”。另一方面，数学家欧拉在证明“欧拉公式”V+F–E=2（其中V是“简单多面体”的顶点数，E是“棱数”F是“面数”）采用了逐步“去线”“去面”“去点”的方法，而本文采用的是先“添线”然后再逐步“去点”与“去线”„反复进行，最终完成了证明。这两种方法虽然不完全相同但却有相似之处。整个证明过程成功的完成主要是依靠一个完善的理论系统。第二种证明方法运用列方程组的方法证明了猜想的正确性。

下面把历史上发生过的著名错误证明以及在各种稿件上见到的典型错误证明介绍如下，最后将简单介绍一下曾经发生过错误的计算机证明的思路。

四色猜想是“用不了一分钟就能说清楚，但即使是全人类的力量，成百年也难以证明”的一个问题。对不了解四色猜想真实含义的业余数学爱好者来说，证明中常犯的错误是认为当今世界的国家和地区只要用四种颜色中的一种染每个国家或地区，是相邻国家或地区具有不同颜色，就算是证明了四色猜想。不能不说这是一个无知的证明。殊不知四色猜想要求证明的是，当国家或地区无限增多，国家或地区的相邻情况任意变化时，也要能证明四种颜色就够了。

1913年，伯克霍夫发现了一些新的可约构形。本世纪三十年代，希施企图用电子计算机在可约构形中找出新的不可免完备集。他提出了判断一个给定构形集合是否为不可免完备集的算法。1961年，有人声称借助于计算机找出了一个不可免完备集，其中的构形是可约的。但是惠特尼和塔特分别独立地发现其错误是计算机误算了一个构形的可约形，同时他们提出了可约形的分类理论。

“四色问题”的被证明解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。

不过不少数学家并不满足于现在找到的证明方法，仍由不少数学家和数学爱好者在寻找更加简洁的证明方法。所以说四色猜想仍然是一个有待数学家继续研究并且不断完善其证明的大问题，更多地需要我们挖掘其潜在的意义。

参考文献：

[1 ]光鲁,龚有限数学引论(第一版)[M],上海科技出版社,1986年5月 288—343页.

[2 ]蔡经球,《离散数学》[M],北京科学出版社,2001年.

[3 ]江泽涵,《多面形的欧拉定理和闭曲面的拓扑分类》第一版[M],人民教育出版社 ,1979年1月

32—42页.

[4 ][美] F•哈拉里著,《图论》第一版[M],上海科技出版社, 1980年1月145-166页.

[5 ]王树禾编著,《图论及其算法》 第一版[M], 中国科技大学出版社出版 , 1990年10月 第一版 1994年8月第二次印刷 141—157页.

[6 ]王朝瑞,《图论》第二版[M] , 北京理工大学出版社 , 2000年.

[7 ]耿素云,《集合论与图论》离散数学第二分册[M],北京大学出版社 , 2000年.

[8 ]颜先邦,《四色定理论证》[J],航空计算科学 , 2003（2）：55-60.

[9 ]颜先邦,《平面图的点着色方法》[J],航空计算科学 , 2003（增刊）：95-98.

[10]王俊邦,《趣味离散数学》[M],北京大学出版社, 2000年.

[11]董德周,《关于最大平面图着色的探讨》[N],科学日报 , 2003-02-27.

[12]徐俊明,《图论及其应用》[M],中国科学技术大学出版社 , 2004 104-245.

[13]丁超,《图的着色条件》[J],暨南大学学报 , 2008 29（1）：35-38.

[14]《Graphs and Combinatorics》[J].Springerlink to Journals 1997 01.

[15]John Adrian Bondy,《Graph Theory with Applications》[M].Elsevier Science.

Student: Yang Caijuan Tutor:Feng Yuan

Abstracts: Four-color theorem is one of the world's three mathematical problems, many mathematicians

are keen on it over the years proved that seeks to find a better non-computer proof, and the

discussion of four-color conjecture and prove greatly promoted the development of graph

theory .

Keywords: Graph Theory Four-color conjecture, four-color proof，Reducible configurations