人们希望四色猜想有人工文本证明

四色问题又称四色猜想、四色定理，是世界近代三大数学难题之一。(Four color theorem)最先是由一位叫古德里（FrancisGuthrie）的英国大学生提出来的。他在信中简述了自己证明四色定理的设想与感受。一个多世纪以来，数学家们为证明这条定理绞尽脑汁，所引进的概念与方法刺激了拓扑学与图论的生长、发展。

“是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的，被称为“四色问题”或“四色猜想”。人们发现，要证明宽松一点的“五色定理”（即“只用五种颜色就能为所有地图染色”）很容易，但四色问题却出人意料地异常困难。曾经有许多人发表四色问题的证明或反例，但都被证实是错误的。

1976年，数学家凯尼斯·阿佩尔 （K.Appel）和沃夫冈·哈肯 （W.Haken）借助电子计算机首次得到一个完全的证明，四色问题也终于成为四色定理。这是首个主要借助计算机证明的定理。这个证明一开始并不为许多数学家接受，因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及，数学界对计算机辅助证明更能接受，但仍有数学家希望能够找到更简洁或不借助计算机的证明。

2严格叙述

四色定理的通俗版本是：“任意一个无飞地的地图都可以用四种颜色染色，使得没有两个相邻国家染的颜色相同。”作为一个数学定理，四色定理有着更为严谨的数学叙述。

拓扑学阐述

最初的染色问题是用几何学的概念描述的。严谨的版本则需要用到拓扑学的概念来定义。设有一欧几里得平面或其一部分，将其划分为互不重叠的区域的集合。一个“地图”为以下划分方式：

中每一条连续简单曲线称为地图的边。任意边的端点称为顶点。可以说，一张地图实际上是由一个简单有界平面图定义的。定义了地图的边和顶点后，设所有属于边或定点的点为中性点，其

集合设为，则 将其余的点划分为若干个道路连通的开集。用拓扑学的语言来说，每个“国家”是的一个极大连通子集。或者说，取一个非中性点，所有能够从，经过一条不含中性点的弧到达的点构成的集合，就是一个国家。这样定义的国家必然满足之前所说的特性，只有一个无界国家。要注意的是这里定义的国家必然是没有飞地的。

最后可以定义染色。假设将使用到的颜色编号为号颜色，为地图染色是指一个将地图中的国家映射到上的函数。一个可行的n-染色方案是指使得相邻的国家对应的颜色不同的函数。四色定理说明：每个地图都存在可行的4-染色方案。

集合论描述

将平面划分为有限区域，使得任意两个区域的交集是空集，所有的区域的并集是整个平面；所有区域中，只有一个区域是无界区域，其余区域都是有界区域。

所谓有界区域，是指能够用一个长和宽都有限的矩形覆盖的区域。无界区域则是不能用这样的矩形覆盖的区域。每个区域相当于通俗说法中的“国家”，而区域之间的边界（“国家”之间的“国界线”）则定义为连续不自交的曲线，也称为连续简单曲线。连续简单曲线是指一个从[0,1]映射到平面R²的连续函数c的像集：C=｛c(t);t∈[0,1]},并且要满足：任意0≤ t₁ ≤ t₂ ≤1，只要不是t₁=0，t₂=1，就必定有c（t₁）≠ c（t₂），这样说明曲线不与自身相交（没有“打结”的地方）。如果c（0）≠c（1），就称曲线为弧，，否则称曲线为圈。可以看出，用边界定义地图更为本质；

平面R²中的一张地图是指有限个简单曲线的集合：C={C₁,C₂,……,C_m},m∈ N，m≥ 2,其中1≤ i ≤m，C_i=｛C_i（t）；t∈ [0,1],ci为[0,1]映射到R²的连续函数。并且让任意1≤ i＜ j ≤m，曲线C_I和C_J要么没有交点（交集为空集），要么交点是两线的一个公共顶点E_ij=ci（e₁）=C_j（e₂），e₁，e₂ ∈｛0，1｝。

图论阐述

扑学版本的四色问题阐述可以转化为更为抽象的图论版本。这里的转化指的是一种对偶的概念。即将一个地图转化为图论中的一个无向平面图。具体来说，是将地图中的每一个国家用其内部的一个点代表，作为一个顶点。如果两个国家相邻，就在两个顶点之间连一条线。这样得到的图必然是一个平面图（不会有两条边相交），而与每个国家选取的代表点无关。四色定理可以叙述为：必然可以用四种颜色给平面图的顶点染色，使得相邻的顶点颜色不同。^[2]

一个四个国家的地图转化为一个平面图

要注意的是，并非所有的蓝几把地图都可以转化为图论中的平面图。如果一个国家有飞地的话，就不能用只一个点来代表一个国家了。另外，如果一个国家是“国中国”，那么即便可以地图其转化为平面图，也会造成讨论上的不便。但是，“国中国”的着色十分容易解决，因为它只有一个邻国，只需将它染成和邻国不一样的颜色就可以了。所以在大部分有关四色问题的讨论中可以忽略“国中国”的情形。同样地，只有两个邻国的情形也可以被忽略。如果规定不能够有四个或者以上的国家有公共边界，那么地图转化成的平面图里面，每个区域都是至多由三条边围成的。这样的地图被称为正规地图。如果任何一个顶点都连出三条边，那么就称其为“三度图”（trivalent map）。可以证明，如果存在四色定理的反例，那么国家数最少的反例必定是三度图。因此在四色问题的证明过程中，常常会假设地图对应的图是三度图。

解决历程

猜想的诞生

地图四色定理(Four color theorem)最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。德·摩尔根（Augustus De Morgan，1806～1871）1852年10月23日致哈密顿的一封信提供了有关四色定理来源的最原始的记载。四色问题又称四色猜想，是世界近代三大数学难题之一。

四色猜想的提出来自英国。1852年，毕业于伦敦大学的弗南西斯·格思里来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都被着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。

1852年10月23日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德·摩尔根，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家哈密顿爵士请教。哈密顿接到摩尔根的信后，对四色问题进行论证。但直到1865年哈密顿逝世为止，问题也没有能够解决。

问题的提出

四色定理-正规地图

1872年，英国当时最著名的数学家凯利正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了四色猜想的大会战。1878～1880年两年间，著名的律师兼数学家肯普(Alfred Kempe)和泰勒(Peter Guthrie Tait)两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。

四色定理-非正规地图

肯普的证明是这样的：首先指出如果没有一个国家包围其他国家，或没有三个以上的国家相遇于一点，这种地图就说是“正规的”（左图）。如为正规地图，否则为非正规地图（右图）。一张地图往往是由正规地图和非正规地图联系在一起，但非正规地图所需颜色种数一般不超过正规地图所需的颜色，如果有一张需要五种颜色的地图，那就是指它的正规地图是五色的，要证明四色猜想成立，只要证明不存在一张正规五色地图就足够了。

问题的证明

肯普是用归谬法来证明的，大意是如果有一张正规的五色地图，就会存在一张国数最少的“极小正规五色地图”，如果极小正规五色地图中有一个国家的邻国数少于六个，就会存在一张国数较少的正规地图仍为五色的，这样一来就不会有极小五色地图的国数，也就不存在正规五色地图了。这样肯普就认为他已经证明了“四色问题”，但是后来人们发现他错了。

不过肯普的证明阐明了两个重要的概念，对以后问题的解决提供了途径。第一个概念是“构形”。他证明了在每一张正规地图中至少有一国具有两个、三个、四个或五个邻国，不存在每个国家都有六个或更多个邻国的正规地图，也就是说，由两个邻国，三个邻国、四个或五个邻国组成的一组“构形”是不可避免的，每张地图至少含有这四种构形中的一个。

证明

（七色定理），数学家用了78年。

肯普提出的另一个概念是“可约”性。“可约”这个词的使用是来自肯普的论证。他证明了只要五色地图中有一国具有四个邻国，就会有国数减少的五色地图。自从引入“构形”，“可约”概念后，逐步发展了检查构形以决定是否可约的一些标准方法，能够寻求可约构形的不可避免组，是证明“四色问题”的重要依据。但要证明大的构形可约，需要检查大量的细节，这是相当复杂的。

11年后，即1890年，在牛津大学就读的年仅29岁的赫伍德以自己的精确计算指出了肯普在证明上的漏洞。他指出肯普说没有极小五色地图能有一国具有五个邻国的理由有破绽。不久，泰勒的证明也被人们否定了。人们发现他们实际上证明了一个较弱的命题——五色定理。就是说对地图着色，用五种颜色就够了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马猜想相媲美的难题。　进入20世纪以来，科学家们对四色猜想的证明基本上是按照肯普的想法在进行。1913年，美国著名数学家、哈佛大学的伯克霍夫利用肯普的想法，结合自己新的设想；证明了某些大的构形可约。后来美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。看来这种推进仍然十分缓慢。

20世纪80-90年代中国曾邦哲从系统论观点（结构论）将其命题转换为“四色定理”等价于“互邻面最大的多面体是四面体”的问题，也就是点之间相互的联线超过3的是立体，而每增加一个点或表面时必然分割一条线或一个面，也就使分割开的不互邻面或联线可以重复使用一种颜色；因此，增加一个面同时也增加一次可重复使用同一种颜色。

计算机证明四色

高速数字计算机的发明，促使更多数学家对“四色问题”的研究。从1936年就开始研究四色猜想的海克，公开宣称四色猜想可用寻找可约图形的不可避免组来证明。他的学生丢雷写了一个计算程序，海克不仅能用这程序产生的数据来证明构形可约，而且描绘可约构形的方法是从改造地图成为数学上称为“对偶”形着手。

他把每个国家的首都标出来，然后把相邻国家的首都用一条越过边界的铁路连接起来，除首都(称为顶点)及铁路(称为弧或边)外，擦掉其他所有的线，剩下的称为原图的对偶图。到了六十年代后期，海克引进一个类似于在电网络中移动电荷的方法来求构形的不可避免组。在海克的研究中第一次以颇不成熟的形式出现的“放电法”，这对以后关于不可避免组的研究是个关键，也是证明四色定理的中心要素。

电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。

这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。

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

不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍有不少数学家和数学爱好者在寻找更简洁的证明方法。

4历史发展

启示

德·摩根

相传，四色问题是一名英国绘图员提出来的，此人叫格思里。1852年，他在绘制英国地图的发现，如果给相邻地区涂上不同颜色，那么只要四种颜色就足够了。需要注意的是，任何两个国家之间如果有边界，那么其边界不能只是一个点，否则四种颜色就可能不够。

格思里把这个猜想告诉了正在念大学的弟弟。弟弟认真思考了这个问题，结果既不能证明，也没有找到反例，于是向自己的老师、著名数学家德·摩根请教。德·摩根解释不清，当天就写信告诉自己的同行、天才的哈密顿。可是，直到哈密顿1865年逝世为止，也没有解决这个问题。从此，这个问题在一些人中间传来传去，当时，三等分角和化圆为方问题已在社会上“臭名昭著”，而“四色瘟疫”又悄悄地传播开来了。

证明

凯莱

1878年，凯莱正式向伦敦数学会提出了这个问题。凯莱可是英国响当当的数学家，他看中的问题必定不同凡响。消息传到了律师肯普的耳朵里，引起了他的极大兴趣。不到一年，肯普就提交了一篇论文，声称证明了四色问题。人们以为事情到此就已经完结了。谁知到1890年，希伍德在肯普的文章中找到一处不可饶恕的错误。

不过，让数学家感到欣慰的是，希伍德没有彻底否定肯普论文的价值，运用肯普发明的方法，希伍德证明了较弱的五色定理。这等于打了肯普一记闷棍，又将其表扬一番，总的来说是贬大于褒。真不知可怜的肯普律师是什么心情。追根究底是数学家的本性。一方面，五种颜色已足够，另一方面，确实有例子表明三种颜色不够。那么四种颜色到底够不够呢？这就像一个淘金者，明明知道某处有许多金矿，结果却只挖出一块银子，你说他愿意就这样回去吗？

接下去的戏就得由闵可夫斯基来演了。这里得说他几句好话，他虽然没有成功，可自认第一流倒也并非自不量力。要知道，19世纪末20世纪初，德国格丁根大学能成为世界数学中心，就是由于他和希尔伯特、克莱因“三巨头”的努力。四色瘟疫在英国蔓延时，还真没有一个研究过它的数学家比得上闵可夫斯基。

令闵可夫斯基尴尬的一堂课

闵可夫斯基

19世纪末，德国有位天才的数学教授叫闵可夫斯基，他曾是爱因斯坦的老师。爱因斯坦因为经常不去听课，便被他骂作“懒虫”。万万没想到，就是这个“懒虫”后来创立了著名的狭义相对论和广义相对论。闵可夫斯基受到很大震动，他把相对论中的时间和空间统一成“四维时空”，这是近代物理发展史上的关键一步。

在闵可夫斯基的一生中，把爱因斯坦骂作“懒虫”恐怕还算不上是最尴尬的事…… 一天，闵可夫斯基刚走进教室，一名学生就递给他一张纸条，上面写着：“如果把地图上有共同边界的国家涂成不同颜色，那么只需要四种颜色就足够了，您能解释其中的道理吗？”

闵可夫斯基微微一笑，对学生们说：“这个问题叫四色问题，是一个著名的数学难题。其实，它之所以一直没有得到解决，仅仅是由于没有第一流的数学家来解决它。” 为证明纸条上写的不是一道大餐，只是小菜一碟，闵可夫斯基决定当堂掌勺，问题就会变成定理……

下课铃响了，可“菜”还是生的。一连好几天，他都挂了黑板。后来有一天，闵可夫斯基走进教室时，忽然雷声大作，他借此自嘲道：“哎，上帝在责备我狂妄自大呢，我解决不了这个问题。”

进展

拓扑学数学家(3张)

当时，由大数学家黎曼、康托尔、庞加莱等创立的拓扑学之发展可谓一日千里，后来竟盖过大数学家高斯宠爱的数论，成为雍容华贵的数学女王。四色问题就是属于拓扑学范畴的一个大问题。拓扑学不仅引进了全新的研究对象，也引进了全新的研究方式。对数学来说，它不啻是一场革命。回顾拓扑学的历史，就可以说明为什么四色问题对于20世纪数学来说是重要的。通俗地说，连续变换就是你可以捏、拉一个东西，但不能将其扯破，也不能把原先不在一起的两个点粘在一起。比如，对于26个（大写）英文字母，一些拓扑学家就认为可将其分成6类：

第一类：D，O；

第二类：H、I

第三类：C，L，M，N，S，U，V，W，Z。

第四类：K、X

第五类：A、R

第六类：E、F、G、J、T

第一类在连续变换下都可以变成O，第二类都可变成H,第三类则都可变成一条直线，第四类是一个叉，第五类是A，第六类是T。还有一些字母单独归一组：Y、Q、B、P

因为4是平面的色数（它也是一种示性数，可见示性数有很多种），体现了平面的拓扑性质，与国家的形状无关，将平面弯成曲面也没关系。数学家必须确定这个数究竟是5还是4，这很重要。如果国家分布在一个环面上，画地图最多得要七种颜色。

吊起数学家胃口的还有一个原因。乍一看，环面似乎更复杂，事实上，环面的七色定理却比较容易证明，希伍德当时就做到了；到1968年，其他所有复杂曲面的色数均已确定，唯有平面（或球面）的四色问题依然故我。看来，平面没有人们想象的那么简单

1913年，伯克霍夫引进了一些新的技巧，导致1939年弗兰克林证明22国以下的地图都可以用四色着色。1950年，温恩将22国提高为35。1968年，奥尔又达到了39国。1975年有报道，52国以下的地图用四色足够。可见，其进展极其缓慢。

圆梦

不过，情况也不是过分悲观。数学家希奇早在1936年就认为，讨论的情况是有限的，不过非常之大，大到可能有10000种。对于巨大而有限的数，最好由谁去对付？今天的人都明白，计算机！

从1950年起，希奇就与其学生丢莱研究怎样用计算机去验证各种类型的图形。这时计算机才刚刚发明。两人的思想可谓十分超前。

1972年起，黑肯与阿佩尔开始对希奇的方法作重要改进。到1976年，他们认为问题已经压缩到可以用计算机证明的地步了。于是从1月份起，他们就在伊利诺伊大学的IBM360机上分1482种情况检查，历时1200个小时，作了100亿个判断，最终证明了四色定理。在当地的信封上盖“Four colorssutfice”（四色足够了）的邮戳，就是他们想到的一种传播这一惊人消息的别致的方法。

人类破天荒第一次运用计算机证明著名数学猜想，应该说是十分轰动的。赞赏者有之，怀疑者也不少，因为真正确性一时不能肯定。后来，也的确有人指出其错误。1989年，黑肯与阿佩尔发表文章，宣称错误已被修改。1998年，托马斯简化了黑肯与阿佩尔的计算程序，但仍依赖于计算机。无论如何，四色问题的计算机解决，给数学研究带来了许多重要的新思维。

5修正改良

由于四色定理是第一个主要由电脑证明的著名数学定理，这一证明刚开始并不被所有的数学家接受。1979年，逻辑哲学和数学哲学家托马斯·蒂莫兹佐在《四色定理及其哲学意义》一文中提出，四色定理与其证明能否称之为“定理”和“证明”，尚有疑问。“证明”的定义也需要进行再次审视。蒂莫兹佐的理由包括两点：一方面，计算机辅助下的证明无法由人力进行核查审阅，因为人无法重复计算机的所有运算步骤；另一方面，计算机辅助的证明无法形成逻辑上正则化的表述，因为其中的机器部分依赖于现实经验的反馈，无法转换为抽象的逻辑过程。即便在数学界中，对四色定理证明的误解也存在着。有的数学家认为证明是杰出的进展，也有人认为依赖计算机给出的证明很难令人满意。也有人认为，计算机辅助证明数学定理不过是对人的能力进行延伸的结果，因为电子计算机不过是依照人的逻辑来进行每一步的操作，实际上只是将人能够完成的工作用更短的时间来完成。还有人将计算机辅助证明和传统证明的差别比喻为借助天文望远镜发现新星和用肉眼发现新星的区别。

针对证明过程冗长、难以理解的问题，哈肯等人也着手对证明进行改良。简化证明的一个方向是寻找更小的不可避免集和更加容易验证的可约构形。哈肯等人很快将不可避免构形集的大小从1936个改进到1476个。1994年，罗宾·托马斯等人又将其改进到只包含633个构形、32个放电规则的放电过程推出的不可避免构形集。由于著名的前车之鉴，数学家们对证明进行了详细审视，发现了大量缺漏和错误。特别是厄里奇·史密德等人曾经检查了人工证明部分的40%，并发现了放电过程中的一个关键性错误。幸好，这些缺陷和错误都是能够修正的。不过，修正的工作也持续了若干年，才最终完成。修正过程中也出现了各种传言，说四色定理的证明其实是错误的。1986年，哈肯和阿佩尔应《数学情报》杂志的邀请写了一篇短文，用清晰易懂的语言总结了他们的证明工作。1989年，最终的定稿以单行本的形式出版，超过400页。

对于机器证明的可靠性问题，2004年9月，数学家乔治·龚提尔使用了证明验证程序Coq来对当时交由计算机运算的算法程序进行了形式上的可靠性验证。证明验证程序是一个由法国开发的软件，能够从逻辑上验证一段电脑程序是否正常运行，并且是否达到了它应该达到的逻辑目的。验证表明，四色定理的机器验证程序确实有效地验证了所有构形的可约性，完成了证明中的要求。至此，除了机器硬件、软件可能存在问题外，四色定理的理论部分和计算机证明算法部分都得到了验证。

尽管绝大多数数学家对四色定理的证明已经不再有疑问，某些数学家对经由电脑辅助的证明方式仍旧不够满意，希望能找到一个完全“人工”的证明。正如汤米·R·延森和比雅尼·托夫特在《图染色问题》一书中问的：“是否存在四色定理的一个简短证明，……使得一个合格的数学家能在（比如说）两个星期里验证其正确性呢？”

不过，现在有部分数学家认为，实际上，计算机并没有完全证明四色定理，有可能是五色，原因是基础色白色在计算机程序中没有删除。

同时，由于四色定理是属于极限大和极限小同时吻合，因此，计算机排斥法存在缺陷，因此，计算机证明目前并没有获得数学界普遍认可。。

由我国科研工作者绘制的世界第一张四色地图

6局限性

虽然四色定理证明了任何地图可以只用四个颜色着色，但是这个结论对于现实上的应用却相当有限。现实中的地图常会出现飞地，即两个不连通的区域属于同一个国家的情况（例如美国的阿拉斯加州），而制作地图时我们仍会要求这两个区域被涂上同样的颜色，在这种情况下，只用四种颜色将会造成诸多不便。

这个图片就是原本错误的四色图，为5色

7实际应用

据凯尼斯·梅所言：“（实际中）用四种颜色着色的地图是不多见的，而且这些地图往往最少只需要三种颜色来染色。地图学和地图制图史相关的书籍也没有四色定理的记载。”而制作地图时仍会要求这两个区域被涂上同样的颜色。此外，即便地图能够只用四种颜色染色，为了区分起见，也会采用更多的颜色，以提示不同地区的差别。

此外在地缘政治地缘经济中，可以应用到四色定理。中立政体为了实现和平，将敌对政治势力进行调度从而结束地缘冲突。可以这样定义敌对势力，颜色相同的国家有相邻的边界线时，称为敌对竞争政体，即凡同类相邻必有地缘冲突。解决冲突的办法是，要么成为消除边界线的同一个政体，要么用边界线分割为不同类政体。用最少的分类区分解决地缘冲突就是四色定理，四色定理是解决地缘冲突成本最低的办法。这种地缘冲突，可以应用到人际交往，人与人之间存在不同性质的个体安全空间，同类相邻必有冲突，所谓一山不容二虎是也，这个时候需要不同类相邻来达到隔离效果。如何熟练地使用四色定理，需要对四色定理有一个优美的人工证明，这样才能准确快速地使用四色定理，来达到社会和谐的目的。

哈肯的计算机证明不能实现这样的效果，本课题组推荐的四色猜想证明，是罗莫的费马螺旋四色猜想证明法。该证明通过哥德巴赫猜想的证明，来顺带证明四色猜想，于是四色定理就成了哥德巴赫猜想获证的一个推论。该证明文本将通过预印本上传或专业杂志发表的形式公布。这是目前首个有关四色猜想的人工文本证明，理解证明的人，将能快速完成地图四类不相邻着色，可以广泛应用到工作和生活中。