四色定理的证明《The Four-Color Theorem 1852–1976》

四色定理的证明《The Four-Color Theorem 1852–1976》

四色定理 

作者：罗宾·威尔逊（Robin Wilson）

四色问题询问的是：在平面上或球面上绘制的任何地图的区域，是否都能用仅四种颜色着色，使得任何两个共享共同边界线的区域获得不同的颜色。该问题由弗朗西斯·格思里（Francis Guthrie）于1852年首次提出，最终由肯尼思·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）在1976年解决，此后被称为四色定理。

为纪念50周年，本文回顾了该证明的故事，特别关注其中涉及的人物。

1. 奥古斯都·德摩根（Augustus De Morgan）

图1. 奥古斯都·德摩根 (1806–1871)

奥古斯都·德摩根（Augustus De Morgan）是新成立的伦敦大学学院的首位数学教授。

他在数学、逻辑学和哲学方面的贡献广为人知，在集合论中以"德摩根定律"（De Morgan’s laws）为人们所铭记。他也是一位多产的数学普及作家，其《悖论集》（Budget of Paradoxes）汇编自他在《雅典娜神殿》（The Athenaeum）（当时的一种文学和科学出版物）上的大量文章，于1872年出版。1865年，他成为伦敦数学学会的首任主席。

多年来，德摩根与爱尔兰数学家威廉·罗恩·哈密顿爵士（Sir William Rowan Hamilton）保持着通信往来，分享他们的新闻、数学传闻和家庭信息。1852年10月23日，他写信给哈密顿说：

❝

我的一个学生今天问我一个事实的理由，而我并不知道，这到底是一个真相，还是不是一个真相。他说，如果一个图形被任意划分，并且各个部分被涂上不同的颜色，使得具有任何共同边界线的图形颜色不同——可能需要四种颜色，但不会更多。……试问，是否是排布的必须性（necessity），需要五种或更多颜色的方案……（注：该问题这里强调的是少于五的必然，不是让给出多颜色的方案）

作为需要四种颜色的地图示例，德摩根画了四个相互毗邻的区域。

后来得知，这位"我的学生"是弗雷德里克·格思里（Frederick Guthrie），他后来成为物理学家和伦敦物理学会的创始者。1880年，他为爱丁堡皇家学会的《会刊》写了一篇注释，将该问题归功于他的哥哥弗朗西斯，弗朗西斯曾是德摩根的学生，当时正在给英格兰地图着色，并询问是否四种颜色对所有地图都足够。弗朗西斯·格思里后来成为南非的数学教授和公认的植物学专家；有几种植物以他的名字命名，包括石楠属植物Erica Guthriei（注：我国多写为格思里石楠）。尽管他从未进一步考虑这个问题，四色问题有时仍被称为"格思里问题"（Guthrie’s problem）。

图2. 弗朗西斯·格思里 (1831–1899)

四色问题也曾被错误地归功于德国数学家和天文学家奥古斯特·莫比乌斯（August Möbius），他在1840年给学生布置了一个关于垂死国王的问题，国王将土地遗赠给他的五个儿子，条件是他们将土地分成五部分，每一部分都与其他四部分相邻。在平面上将土地分成五个相互毗邻的区域会产生一张需要五种颜色的地图，但证明其不存在并不能证明四色定理——这是在该问题历史上多次出现的误解。

德摩根对这一挑战着迷，并向他的朋友和同事询问其解决方案是否已得到，但始终没有得到答案。从一开始，他就错误地认为证明将关键依赖于以下观察：如果一张地图包含四个相互毗邻的区域，那么其中一个必须被其他三个所包围。当他向四元数代数系统的发明者哈密顿提及此事时，他收到了简短但恰当的回复：我不太可能在短期内尝试你的「色四元数」。

四色问题最早的已知印刷描述出现在1854年，当时一段题为"地图着色"的文字出现在《雅典娜神殿》的专栏中。署名"F. G."，可能是弗雷德里克或弗朗西斯·格思里寄来的，也可能是当时正在寻求加入伦敦雅典娜神殿俱乐部的地理学家和博学家弗朗西斯·高尔顿（Francis Galton）寄来的。

同一期刊的后续提及出现在1860年，当时德摩根撰写了一篇未署名的书评，由于他的注释，四色问题传到了美国，引起了查尔斯·桑德斯·皮尔斯（Charles Sanders Peirce）的注意；皮尔斯后来成为杰出的逻辑学家和哲学家，当时正在哈佛大学学习，他的父亲本杰明·皮尔斯（Benjamin Peirce）是当时美国最杰出的数学家。年轻的查尔斯向哈佛的数学学会提出了一个解决方案，但现在不知其形式如何。

2. 亚瑟·凯莱（Arthur Cayley）

德摩根于1871年去世，直到最后他也不知道四色定理是否成立，这个问题似乎也随他而去。但七年后，在伦敦数学学会的一次会议上，剑桥数学家亚瑟·凯莱重新提出了这个问题。

图3. 亚瑟·凯莱 (1821–1895)

亚瑟·凯莱（Arthur Cayley）出生于伦敦，但在俄罗斯度过了他的早年岁月，他的父亲在那是一名商人。返回英格兰后，他在伦敦接受学校教育，17岁时进入剑桥大学三一学院。1840年以优异成绩毕业后，他被任命为学院研究员，但由于需要接受英国圣公会圣职，他于1844年离开剑桥，在伦敦的律师学院做了19年成功的律师。在此期间，他写了300多篇数学论文，并结识了他的朋友和合作者詹姆斯·约瑟夫·西尔维斯特（ James Joseph Sylvester），与他一起发展了不变量理论这一新的代数课题。1863年，他返回剑桥担任首任萨德勒里安（Sadleirian）纯数学教授，这一职位他一直担任到去世。（注：该职位隶属于剑桥大学‌纯数学与数理统计系‌（DPMMS），是英国数学界最高荣誉职位之一）

继德摩根之后，西尔维斯特和凯莱相继成为伦敦数学学会的主席。19世纪70年代，凯莱开始从事化学分子的计数工作，而西尔维斯特探索分子与代数不变量之间的所谓联系，导致他在1878年引入了"图"这个词（在图论的意义上）。

1875年，五年前从伍尔维奇皇家军事学院退休的西尔维斯特被任命为新成立的巴尔的摩（Baltimore）约翰·霍普金斯大学的首任数学教授。在那里，他建立了一个数学研究学派，并协助创办了《美国数学杂志》（American Journal of Mathematics）；该杂志包含新兴美国数学家的文章以及稳定的欧洲数学家的文章。

1878年6月13日，凯莱出席了伦敦数学学会的一次会议，在那里他询问用四种颜色给地图着色的问题是否已解决。他很快对这个问题产生了兴趣，并应朋友弗朗西斯·高尔顿的邀请，为皇家地理学会的《会刊》写了一篇题为"论地图着色"的简短笔记。

在这篇笔记中，凯莱承认他无法找到证明，并试图解释困难可能在哪里。更有用的是，他解释了如何将一般问题简化为三次地图的情况——即每个交汇点恰好有三个区域的地图。因为无论在哪里有超过三个区域交汇，我们都可以在该点上贴一个"补丁"，从而得到一个三次地图（见图4）。如果这张地图能用四种颜色着色，我们就可以将每个补丁收缩到一个点，从而产生原始地图的着色。这是一个重要的进展：从那时起，地图着色者将注意力集中于三次地图即可。

图4. 三次地图的四色问题

3. 阿尔弗雷德·肯普（Alfred Kempe）

图5. 阿尔弗雷德·肯普 (1849–1922)

参加6月13日会议的人之一，阿尔弗雷德·布雷·肯普（Alfred Bray Kempe），他是一名律师，曾是凯莱在三一学院的数学学生。肯普相信他能为四色定理提供证明，经过几个月的研究，他撰写了一篇论文[9]，应主编西尔维斯特的邀请，提交给《美国数学杂志》，并在该杂志上发表。他还向科学期刊《自然》发送了预览。

[9] A. B. Kempe, On the geographical problem of the four colours, Amer. J. Math. 2 (1879), no. 3, 193–200, DOI 10.2307/2369235. MR1505218

在他的论文中，肯普证明了每个三次地图必须包含至少一个边界边数不超过五的区域——即二边形、三角形、四边形或五边形。要理解原因，我们使用欧拉多面体公式，该公式表明对于任何具有个区域、条边和个区域交汇点的平面地图，N-E+R=2。如果C_k是具有k条边的区域数，那么3N=2E（因为每条边连接两个点），因此R=C₂+C₃+C₄+C₅+...,

2E=3N=2C₂+3C₃+4C₄+5C₅+6C₆+7C₇

将这些表达式代入欧拉公式得到计数公式

4C₂+3C₃+2C₄+C₅-C₇-2C₈-...=12

因此，如果没有边界边数不超过五的区域，左边将为负数，我们将得到矛盾。

如果地图包含二边形或三角形，那么归纳证明是直接的：我们只需给地图的其余部分着色，然后就会有一种剩余的颜色可以用来给它着色。但如果地图包含一个四边形，它可能被所有四种颜色的区域包围（比如说，按顺序为红、蓝、绿、黄）。为了处理这种情况，肯普提出了一个涉及颜色互换的有效论证，后来被称为肯普链方法。

图6. 肯普链方法

肯普观察了相邻部分的红-绿部分（见图6）。如果它们没有连接起来，那么在其中一部分互换红色和绿色就会为留下一种剩余的颜色。但如果它们通过红-绿区域链连接起来，那么互换红色和绿色并不能改善情况。但在这种情况下，相邻的蓝-黄部分被红-绿链隔开，因此可以在一部分中互换蓝色和黄色，再次为留下一种剩余的颜色。因此，在任何情况下，四边形都可以着色，结果再次通过归纳得出。

然后肯普转向地图包含五边形的剩余情况。如果地图的其余部分已经着色，并且如果被所有四种颜色包围且有一种颜色出现两次，那么进行两次颜色互换将消除该颜色的两次出现。然后就会有一种剩余的颜色给，证明就完成了。

这似乎处理了所有可能的情况，但正如我们将发现的，肯普的最后一步是有缺陷的，他的论证后来被认为是有史以来最著名的错误证明之一。

更有价值的是，肯普还引入了另一个想法。任何地图区域的着色都会产生其首都的着色（见图7）。如果我们然后连接每对相邻区域的首都，我们就得到了肯普所称的链。四色问题就变成了用四种颜色给这些首都着色的问题，使得任何两个相连的获得不同的颜色。正如我们将看到的，这个问题的对偶形式，用地图区域的着色替换为平面图顶点的着色，后来成为标准表述。

图7. 链的着色

当肯普提交他的证明时，西尔维斯特在夏天访问英格兰期间不在城里，论文由他的约翰·霍普金斯同事威廉·斯托里（William Story）处理，斯托里是杂志的联合创始人和副主编。虽然没有发现肯普的主要错误，斯托里看到了如何填补肯普论证中的一些小漏洞，并写了一篇简短的"关于前述论文的注释"放在肯普的证明之后。斯托里对四色问题的迷恋持续多年，在肯普的错误被发现后，他与C. S. 皮尔斯（C. S. Peirce）就此事进行了通信。

与此同时，阿尔弗雷德·肯普撰写了多篇关于机械连杆几何性质（geometrical properties of mechanical linkages）的著名论文，并因这些论文以及他对四色问题的所谓解决方案，于1881年当选为伦敦皇家学会会员。他后来成为该学会的财务主管，并以这一身份资助了一次重要的南极探险，后来的肯普冰川和肯普山就是以他的名字命名的。

4. 彼得·格思里·泰特（Peter Guthrie Tait）

肯普的"证明"被广泛接受为四色问题的解决方案。但在苏格兰，数学物理学家彼得·格思里·泰特（Peter Guthrie Tait）在1880年爱丁堡皇家学会的《会刊》中发表了一篇注释，批评肯普的论证过于复杂，对问题缺乏洞察力。作为回应，泰特提出了一些更短更简单的证明，所有这些证明都是有缺陷的。

图8. 彼得·格思里·泰特 (1831–1901)

同年晚些时候，泰特提出了一个更具建设性的想法，他证明了用四种颜色给三次地图的区域着色，等价于用仅三种颜色给边界边着色，使得每个交汇点的三条边颜色不同（见图9）。他认为这种替代表述比原始版本更容易证明。虽然他在这点上错了，但边着色（edge-colorings）这一课题后来成为重要的研究课题。

图9. 泰特的重新表达

随着肯普的证明被认为是该问题的最终结论，其他数学家开始对这个问题感兴趣。牛津数学讲师查尔斯·L. 道奇森（Charles L. Dodgson）（更广为人知的名字是《爱丽丝梦游仙境》的作者刘易斯·卡罗尔 Lewis Carroll）将其作为两人游戏。而在布里斯托尔（Bristol）附近的克利夫顿学院这所私立学校，校长可能想起了泰特的简短"证明"，将其作为学校的挑战性问题提出，“任何解决方案都不得超过一页、30行手稿和一页图表。”

他还将其发送到《教育杂志》供读者尝试。一位这样做的读者是伦敦主教弗雷德里克·坦普尔（Frederick Temple），他曾是牛津大学的数学讲师，后来成为坎特伯雷大主教，他在一次乏味的会议中走神时找到了一个解决方案。但他所做的只是证明了在平面上五个相邻区域不可能存在，正如我们前面指出的，这并不能证明该结果。

5. 珀西·希伍德（Percy Heawood）

1890年，一篇题为"地图着色定理"[10]的开创性论文发表，该论文将使这个问题的解决再推迟86年。其作者是珀西·约翰·希伍德（Percy John Heawood），他在牛津大学学习数学时了解到四色问题。获得牛津学位后，他转到达勒姆学院（后来的达勒姆大学），在那里度过了余生。他是一个受人喜爱但有些古怪的人物，每年只在圣诞节校准一次手表，并认为如果未能参加至少一次委员会会议，这一天就被浪费了。

[10] P. J. Heawood, Map-colour theorem, Quarterly J. Pure and Applied Math. 24 (1890), 332–338.

图10. 珀西·希伍德 (1861–1955)

自牛津求学时代起，就对四色问题着迷的希伍德，惊讶地发现肯普的证明尝试中存在根本性缺陷。

在他的论文中，他指出，在处理五边形时，肯普假设可以同时进行两次颜色互换，但希伍德提出了一个具体的例子，说明这是无法做到的。在他的例子中（见图11），未着色的五边形位于中心，可以在五边形上方进行红-绿颜色互换，或在五边形下方进行红-黄颜色互换，但如果两者同时进行，那么图中右侧的绿色和黄色区域都会变成红色，这是不允许的。

图11. 希伍德的例子

幸运的是，希伍德能够通过调整肯普的论证来证明每张地图都可以用五种颜色着色——这本身就是一个重要的结果。

希伍德还讨论了一个相关问题，即帝国问题（empire problem），其中每个国家有一个卫星区域，必须与母国获得相同的颜色。他证明了所有这样的三次地图都可以用十二种颜色着色，并"极其困难地"获得了一个需要全部十二种颜色的具体例子（见图12）。请注意，每个由两部分组成的帝国都与其他所有帝国相邻。

接下来，在观察到在平面上绘制地图等价于在球面上绘制地图后，希伍德研究了在其他可定向表面上绘制三次地图所需的色数，例如添加了个手柄的球面。例如，环面上的每张地图都可以用七种颜色着色，希伍德展示了一个使用全部七种颜色的环面地图。

图12. 帝国问题

但希伍德也犯了错误。对于在表面S(g)上具有个R区域、E条边和N个点的三次地图，欧拉公式告诉我们N-E+R=2-2g。从这个结果希伍德推导出其区域可以用|1/2(7+√(48g+1))|种颜色着色，但对于所有g>1，他未能证明实际上需要这么多颜色的地图存在，这一断言后来被称为希伍德猜想（Heawood conjecture）。直到1968年才被完全证明（见[2]和[3]）。

[2] Robin Wilson, John J. Watkins, and David J. Parks, Graph theory in America—the first hundred years, Princeton University Press, Princeton, NJ, 2023, DOI 10.2307/j.ctv2sbm8p2. MR4574842

[3] Lowell W. Beineke, Bjarne Toft, and Robin J. Wilson, Milestones in graph theory—a century of progress, AMS/MAA Spectrum, vol. 108, MAA Press, Providence, RI, 2025. MR4922623

1898年，希伍德写了第二篇论文，其中他将四色问题重新表述为数值同余的形式。他首先证明，泰特对三次地图边的着色对应于给交汇点分配数字和，使得每个区域周围的数字之和是3的倍数（见图13）。此外，如果点被标记为，那么对于每个区域都有一个同余 (mod 3)，其中每个是或，并且每当点位于该区域的边上时，就出现在同余式中。

图13. 希伍德对三次地图点的标记

在他对四色定理证明的终身探索中，希伍德继续探索他的同余式，以在他90岁时发表的一篇论文作为结束。

6. 保罗·韦尼克（Paul Wernicke）

希伍德的揭露之后，肯普试图纠正他的证明，但没有成功。一些数学家甚至对该结果是否成立表示怀疑，丹麦数学家朱利叶斯·彼得森（Julius Petersen）评论道：

❝

我什么都不确定，但如果要下注，我会坚持认为四色定理是不正确的。

同时，大约在那段时间，德国数学家赫尔曼·闵可夫斯基（Hermann Minkowki）正在哥廷根大学讲授位置分析（拓扑学）。他声称，未能证明四色定理是因为只有三流数学家尝试过这项任务，他向学生吹嘘他能找到证明。随后几周，他尝试但未成功，最后不得不承认他也失败了。

20世纪的第一个新想法归功于保罗·韦尼克（Paul Wernicke）。他于1866年出生于德国，在1893年移居美国并成为美国公民之前获得了数学学位。他在肯塔基州找到了教授现代语言的工作，但依然对数学感兴趣，后来返回德国撰写了一篇关于位置分析的博士论文，然后又回到美国。

韦尼克长期对四色问题感兴趣。在德国期间，他为《数学年鉴》（Mathematische Annalen）撰写了一篇重要论文，其中他证明了任何没有二边形、三角形或四边形的三次地图，不仅必须包含五边形，还必须包含两个相邻的五边形或一个与六边形相邻的五边形（见图14）。他希望这最后两种构型比简单的五边形更容易研究。

图14. 韦尼克的不可避免集

由此产生了地图中不可避免集构型的基本概念。具有环大小的构型由一个或多个被个其他区域环包围的区域组成，如图15所示，如果每个三次地图必须包含至少其中一个，则一组构型是不可避免的。这一概念起源于肯普并由韦尼克发展，在后来对四色问题的尝试中被证明是至关重要的。

图15. 环大小为14的构型

7. 奥斯瓦尔德·维布伦（Oswald Veblen）

1912年是四色问题的重要一年，两篇由美国人撰写的重要论文出现在《数学年刊》（Annals of Mathematics）上。这些论文由奥斯瓦尔德·维布伦（Oswald Veblen）和乔治·伯克霍夫（George Birkhoff）撰写，加上伯克霍夫次年的一篇开创性论文，开启了四色问题进展的新时期。

图16. 奥斯瓦尔德·维布伦 (1880–1960)

奥斯瓦尔德·维布伦（Oswald Veblen）出生于爱荷华州，在爱荷华大学（他14岁入学）和哈佛大学接受教育。然后他转到芝加哥大学，在那里他获得了几何学博士论文的博士学位，这是他最为人铭记的数学领域。从1905年到1932年，他在普林斯顿大学任教，然后成为新建高等研究院的首任数学教授。

在他关于"位置分析中模方程的应用"的论文中，维布伦使用几何和代数的思想来阐述四色问题。他首先引入了两个矩阵来指定具有给定顶点（交汇点）、边界边和区域标记的地图：这些是顶点-边关联矩阵（ vertex–edge incidence matrix），其项如果顶点位于边上则为1，否则为0；以及边-区域关联矩阵（edge–region incidence matrix），其项如果边与区域相邻则为1，否则为0。

这些矩阵中的每一个都导出两组线性方程；例如，对于矩阵，方程中的变量代表地图的区域，每条边对应一个形式为的方程，其中和代表沿该边相遇的区域。将具有四个元素的有限域的元素作为四种颜色，维布伦证明四色问题的解在于找到一组满足这些方程的值。

然后维布伦进一步发展这些思想，用有限射影空间的子空间来表达四色问题。他还展示了如何从矩阵得出一组方程，等价于我们前面遇到的希伍德同余式。

8. 乔治·伯克霍夫（George Birkhoff）

1912年初，维布伦在普林斯顿的一位朋友，同时代人，乔治·戴维·伯克霍夫（George David Birkhoff），是20世纪初最全能和最有影响力的数学家之一。他出生于密歇根州，从小就显示出巨大的潜力。1902年他就读于芝加哥大学，在那里他第一次遇到维布伦。在那里一年后，他转到哈佛大学获得学士和硕士学位，然后返回芝加哥撰写关于微分方程的博士论文。在接下来的两年里，他在威斯康星大学度过，然后转到普林斯顿，在那里被提升为教授。1912年他返回哈佛大学，在那里度过了余生。

图17. 乔治·伯克霍夫 (1884–1944)

虽然伯克霍夫最出名的是在动力系统、微分方程、遍历理论和其他领域的工作，但他对四色问题有着终生的迷恋。为了寻找证明，他常让妻子为他绘制复杂的地图供他着色。

伯克霍夫对地图着色的第一种方法是定量的，询问用种颜色给给定地图着色的方式数；例如，对于四个相互毗邻区域的地图，这是

P(k)=k(k-1)(k-2)(k-3)=k⁴-6k³+11k²-6k

他证明了P(k)总是k的多项式（现在称为地图的色多项式），表明如果地图有n个区域和m条边，那么P(k)以kⁿ-mk^n-1开始，并获得了其他每个系数的公式。通过一般地研究这些多项式，他希望证明对所有地图p(4)>0。

伯克霍夫对色多项式的兴趣持续了一生，1930年和1934年他发表了关于该主题的进一步论文。前者由哈斯勒·惠特尼（Hassler Whitney）（后来成为开拓性的拓扑学家）撰写，他对四色问题的想法给伯克霍夫留下了深刻印象，并在伯克霍夫的指导下撰写了关于图着色的博士论文；惠特尼还发表了一篇关于色多项式的著名论文，其中他提出了一种计算系数的更简单方法，并证明这些系数总是交替变号。后来，伯克霍夫（去世后）与他的前研究生丹尼尔·C. 刘易斯（Daniel C. Lewis）合作发表了一篇关于该主题的长篇有影响力的联合论文。

1913年，在一篇开创性的论文[11]中，Birkhoff对四色问题的最终解决做出了重大贡献，他描述了一种配置是可还原的，如果周围区域环的每种颜色都可以扩展到内部区域。由此可知，一个可约构型不能对四色定理进行最小的反证。

[11] George D. Birkhoff, The reducibility of maps, Amer. J. Math. 35 (1913), no. 2, 115–128, DOI 10.2307/2370276. MR1506176

在系统地证明每个被三或四个区域环包围的构型都是可约的之后，伯克霍夫继续研究环大小为5的构型，并证明除了单个五边形之外，这些都是可约的。

他还证明了被六个区域环包围的四个五边形的伯克霍夫钻石（图18）是可约的。这里周围环本质上只有31种不同的着色；其中16种直接扩展到五边形，而其余15种在一次或多次肯普颜色互换后实现。

在随后的几年里，人们发现了更多的可约构型，最终达到了成百上千。

图18. 伯克霍夫钻石

9. 菲利普·富兰克林（Philip Franklin）

在1920年代和1930年代，该问题的进展稳步推进中。1921年，比利时数学家阿尔弗雷德·埃雷拉（Alfred Errera）为布鲁塞尔大学撰写了一篇关于地图着色的博士论文，并随后发表了几篇进一步的论文，特别是证明了四色定理的每个最小反例必须包含至少13个五边形，并且不能仅包含五边形和六边形。

与此同时，在美国，菲利普·富兰克林（Philip Franklin）已出现在历史舞台上。他是纽约城市学院的毕业生，转到普林斯顿大学，在奥斯瓦尔德·维布伦（Oswald Veblen）的指导下完成了题为"四色定理"的博士论文。随后他发表了一篇重要论文[12]，扩展了当前关于不可避免集和可约构型的知识。1924年，他转到麻省理工学院，在那里度过了余生，在各个领域进行研究并撰写了多本广受好评的学生教科书。

[12] Philip Franklin, The four color problem, Amer. J. Math. 44 (1922), no. 3, 225–236, DOI 10.2307/2370527. MR1506473

在他的论文中，富兰克林使用肯普的计数公式发现了更多的可约构型，例如与三个五边形相邻的五边形，以及与四个五边形和两个六边形相邻的六边形。他还证明了每个没有二边形、三角形或四边形的地图必须包含一个与另外两个五边形相连的五边形，或与两个五边形和一个六边形相连的五边形，或与一个五边形和两个六边形相连的五边形；这产生了图19中的新不可避免集。直到1940年，当亨利·勒贝格（勒贝格积分的发明者）在他撰写的最后一篇论文中导出几个新的不可避免集时，才出现进一步的不可避免集。

图19. 富兰克林的不可避免集

富兰克林还推断出每个多达25个区域的地图都可以用四种颜色着色。随后，西弗吉尼亚大学的克拉伦斯·雷诺兹（Clarence Reynolds）进行了进一步的工作，将这个数字增加到27，而C. E. 温恩（C. E. Winn）在1940年进一步将其增加到35。

10. 海因里希·希施（Heinrich Heesch）

二战后，随着德国数学家海因里希·希施（Heinrich Heesch）的出现，证明四色定理的尝试开始转向不同的方向。他出生于基尔，在慕尼黑获得数学和音乐学位，然后在苏黎世大学获得几何学公理的博士论文博士学位。然后他转到哥廷根大学，成为赫尔曼·外尔（Hermann Weyl）研究晶体的助理。在那里，他因解决平面瓷砖图案的"规则镶嵌问题"（regular parquet problem）而获得了一些恶名；这是大卫·希尔伯特1900年在巴黎国际数学家大会上发表著名演讲时提出的挑战中的“第18问题”的一部分。

[译者注：Heinrich Heesch 因提出 ‌“Heesch数”‌ 概念并系统研究‌非周期性镶嵌的可能性‌，挑战了当时数学界根深蒂固的“所有平面镶嵌必为周期性”的共识，从而获得“恶名”。这一“恶名”并非源于学术错误，而是因其观点在当时被视为‌对几何直觉的颠覆‌，遭到主流学界的排斥与边缘化。]

但从1933年开始，纳粹对德国大学教职员工的清洗使学术生活变得无法忍受，希施辞去了他在哥廷根的职位。回到基尔，他与父母一起度过了接下来的十几年，通过学校教学维持生计，同时继续他对镶嵌图案的研究；其中一种图案后来被纳入哥廷根图书馆的天花板设计中。

希施在1930年代中期首次了解到四色问题，并对其产生了终生的迷恋。他很快意识到，为了解决这个问题，他应该寻找一个可约构型的不可避免集——"不可避免"意味着每张地图必须包含这些构型中的一个或多个，"可约"意味着无论它是哪一个，地图其余部分的每种着色都可以扩展到该构型。换句话说，因为不可避免集中的可约构型都不能出现在四色定理最小反例中，所以这样的反例不可能存在。

大约在1948年，希施在基尔向大量听众做了关于四色问题的讲座。提出需要一个有限的可约构型不可避免集，他承认这样一个集可能非常大——可能涉及多达10,000个构型。为了帮助它们的分类，他将一个构型定义为D-可约的：如果周围环中区域的任何着色都可以直接或经过颜色互换扩展到该构型。正如我们所见，二边形、三角形、四边形和伯克霍夫钻石都是-可约的。他还称构型为C-可约的，如果它可以通过以某种方便的方式修改而变成可约的。

与此同时，希施在构建大量的可约构型，多年来他发展出了通过目测识别构型何时可约的能力——最终准确率超过80%。为此，他注意到三个似乎阻止构型可约的特征——这些是一个与周围环四个连续区域相邻的"4-腿区域"（4-legger region），一个与周围环三个区域（并非全部相邻）相邻的"3-腿连接区域"（3-legger articulation region），以及一对都与环内单个区域相邻的相邻五边形的"悬挂5-5对"（hanging 5-5 pair）（见图20）。

图20. 可约性的三个障碍

正如我们所指出的，当时已知的不可避免集很少，但希施发现了一种证明给定构型集是不可避免的有用方法。这被称为放电法（method of discharging），有多种形式，但为了说明基本思想，我们可以展示为什么韦尼克的构型集（图14）是不可避免的。

证明：假设存在一个矛盾，即没有二边形、三角形或四边形、没有两个相邻五边形、也没有五边形与六边形相邻的地图；那么每个五边形只与有七条或更多边的区域相邻。接下来，给每个边形区域分配的"电荷"，因此五边形获得单位电荷，六边形获得零电荷，超过六边的多边形获得负电荷。然后根据肯普的计数公式，整张地图的总电荷为12，一个正数。如果我们现在通过将每个五边形的单位电荷平均分配给它的五个邻居来"放电"地图，那么地图上的总电荷保持为正，但现在每个五边形有零电荷，六边形仍有零电荷，并且（容易验证）其他区域获得的电荷不足以变为正数。由此得出地图上的总电荷为非正数，这个明显的矛盾证明了结果。

到这个时候，图论这一学科正在发展，大多数地图着色者以四色问题的"对偶形式"工作——即在肯普的链版本中。在这里，目标不是给地图着色使相邻区域获得不同颜色，而是给平面图的顶点着色，使任何两个相邻顶点颜色不同。为此，希施引入了对应于五边形、六边形等的顶点的方便符号（见图21）。在后来的几年里，这些几乎被普遍使用。

图21. 希施对地图区域的符号

11. 沃尔夫冈·哈肯（Wolfgang Haken）

沃尔夫冈·哈肯（Wolfgang Haken）1928年出生于柏林，从小就表现出对数学的兴趣。15岁时，他被征召参加第二次世界大战的高射炮部队，同时继续他的学业，并于1946年初完成。当时，大多数德国大学不接受23岁以下的学生，但基尔大学是个例外，哈肯17岁时就在那里开始学习，是大学里最年轻的学生。在学年中间被录取学习数学、物理和哲学，他直接被抛进了第二学期的课程，而没有学习早期基础。但他设法赶上了，后来将这一时期描述为"真的非常，非常令人兴奋——对我来说，那是美好的岁月"。

当时基尔只有一位活跃的数学教授，卡尔-海因里希·魏泽（Karl-Heinrich Weise）。作为一位优秀的教师，1947年他教授了一门拓扑学课程，其中提到了三个未解决的问题：纽结问题、庞加莱猜想和四色问题。这三个问题后来占据了哈肯生活的主要部分，他解决了第一个，对第二个做出了重大贡献，并最终与肯尼思·阿佩尔（Kenneth Appel）合作解决了第三个。

在基尔，哈肯认识了海因里希·希施并参加了关于四色问题的讲座。他当时对此理解甚少，但后来回忆说，希施需要系统地处理大约10,000个特殊情况才能获得证明。这次谈话在哈肯的脑海中播下了一颗种子，将在几十年后结出果实。

1948年获得学位后，哈肯在魏泽的指导下开始研究生学习，1953年获得关于高维拓扑的博士论文博士学位。然后他搬到慕尼黑，在西门子公司的研发部门从事微波技术工作。

在慕尼黑期间，哈肯保持了对数学的兴趣，特别是对判断给定的三维闭合曲线（如一团绳子）是否有纽结的"纽结问题"感兴趣。他在业余时间研究这个问题，最终成功提出了一个完整的解决方案，他在1954年阿姆斯特丹国际数学家大会上宣布了这一方案。他的困难在于在继续全职工作的同时找到时间写出完整的证明以供发表，但这一任务最终完成，他的长篇证明发表在《数学学报》（Acta Mathematica）上。

阅读哈肯证明的学者之一是伊利诺伊大学厄巴纳-香槟分校的逻辑学家比尔·布恩（Bill Boone）。他印象深刻，邀请哈肯到该大学担任访问教授，在那里哈肯就他对问题的解决方案做了讲座。然后他在普林斯顿高等研究院度过了两年，然后返回伊利诺伊大学在该校担任永久职位。

哈肯然后将注意力转向证明庞加莱猜想。他对每个困难问题的方法都是将其视为一棵有许多叶子和分支的树，然后一次砍掉一个，直到整棵树被推倒。对于庞加莱猜想，他发现有200片叶子需要移除，并声称已经移除了198片。但在与最后两片斗争了十年后，他终于承认失败。

1967年，厄伊施泰因·奥雷（Oystein Ore）出版了第一本关于四色问题的书[6]，同年哈肯将注意力转向了他近二十年来忽视的主题。他首先决定联系希施，以确定后者是否解决了四色问题，或者他是否仍在处理他的10,000个特殊情况。此时，希施已经产生了数千个可约构型，但未能将它们打包成一个不可避免集。

[6] Oystein Ore, The four-color problem, Pure and Applied Mathematics, vol. 27, Academic Press, New York-London,1967. MR216979

哈肯邀请希施到伊利诺伊大学做关于四色问题的讲座，并问他增加计算机的使用是否可能有助于检查如此多的构型。希施当时在汉诺威自由大学工作，已经雇用了一位名叫卡尔·杜尔（Karl Dürre）的前研究生在大学当时的计算机上测试构型的-可约性；对于任何给定的构型，这可以通过检查周围环的所有着色是否可以直接或在颜色互换后扩展到内部区域来常规完成。

我们已经看到，对于环大小为6的伯克霍夫钻石，周围环本质上只有31种不同的着色需要检查。但随着构型复杂性的增加，着色数急剧增加——环大小每增加一个单位就增加4倍——对于环大小为14的构型，需要考虑199,271种着色。有如此多的构型需要检查，任何当时计算机所需的数千小时似乎都无法实现。

伊利诺伊大学没有现成的计算机可供使用，但其计算机部门能够为希施和杜尔安排使用长岛布鲁克海文国家实验室强大的克雷计算机。其主任，岛本义雄（Yoshio Shimamoto），本人也对四色问题着迷，邀请他们在布鲁克海文度过长时间。当时已经知道，任何解决方案必然涉及环大小为12或更大的构型，克雷计算机当时使他们能够检查许多环大小为13的构型的-可约性，同时开始处理环大小为14的构型。

在调查的一个阶段，岛本发现了一个单一的构型，即所谓的"岛本马蹄铁"（Shimamoto horseshoe），环大小为14，其预期的-可约性将完全证明四色定理。谣言迅速传遍世界，但在漫长的26小时运算后，计算机最终确认，令所有人失望的是，马蹄铁构型不是-可约的。

12. 肯尼思·阿佩尔（Kenneth Appel）

大约在1970年，希施发展了一些新的放电过程，他相信这些过程会将四色问题简化为8,900个环大小不超过18的棘手构型，然后可以单独测试。但此时哈肯对不得不处理这么多困难案例的前景感到失望，在他在伊利诺伊大学做的一次讲座中，他宣布：

❝

计算机专家告诉我，不能再这样继续下去。现在我要退出了。我认为这是人们可以在没有计算机的情况下达到的不能超越的极限。

参加哈肯讲座的人之一是肯尼思·阿佩尔（Kenneth Appel），他为密歇根大学撰写了一篇关于数理逻辑与代数之间某些联系的博士论文。作为一名技能高超的计算机程序员，他在密歇根期间学会了计算技能，他的职业生涯包括在道格拉斯飞机公司工作和在普林斯顿国防分析研究所做研究，然后于1961年转到伊利诺伊大学。

在讲座时，阿佩尔是哈肯的一位研究生的评审之一，而其课题正是关于四色问题某方面的博士论文，在哈肯的声明后，他接近哈肯并提出了一个建议：

❝

我不知道有什么涉及计算机的事情是做不到的：有些事情只是需要比其他事情更长的时间。我们为什么不试一试呢？

图22. 肯尼思·阿佩尔 (1932–2013) 和沃尔夫冈·哈肯 (1928–2022)

到目前为止，大多数地图着色者在试图将它们打包成不可避免集之前，先大量寻找可约构型，但都未成功。但哈肯的方法不同，他寻求开发由看起来"可能可约"的构型组成的不可避免集，然后测试这些构型的可约性。任何不容易证明是可约的构型都将被其他构型替换。他希望这种迭代过程能更快地导出可约构型的不可避免集。

当阿佩尔和哈肯开始实验这个想法时，计算机输出的最早构型包含许多重复，但阿佩尔很快引入了一些简单的修改来减少列表。这很快成为一个持续的实验过程，阿佩尔和哈肯定期调整放电算法并改进计算机程序以优化列表。

为了简化问题，他们将注意力限制在不包含希施三个可约性障碍的构型上，因为这些不太可能出现在最终的不可避免集中。最初集中于排除前两个障碍（4-腿和3-腿区域）的"地理上良好"的构型，他们开始相信在几个月内产生地理上良好构型的不可避免集确实在可能范围内。考虑到这一点，他们然后花了1974年的几个月发展了一个理论论证，确认了这样一个不可避免集确实存在，并具有可实现的构建方法。

渐渐地，阿佩尔和哈肯意识到，虽然-可约构型通常是可处理的（如果它们不是太大），但-可约构型需要一些帮助，其中修改是必要的，但其性质不清楚。在联系大学的计算机科学系时，阿佩尔发现一位名叫约翰·科赫（John Koch）的研究生愿意帮忙。阿佩尔让他找到修改环大小为11的-可约构型的简单方法，当科赫成功做到这一点时，阿佩尔随后将科赫的想法扩展到更大环大小的构型。

1975年，阿佩尔和哈肯引入了希施的第三个可约性障碍（悬挂5-5对），并欣慰地发现，程序中的相应变化只会使不可避免集的大小增加一倍。在这些月份里，他们继续做出的各种改进很快导致了"人机对话"，其中计算机似乎发现了它自己改进那些已经被明确编程的方法。

他们已经开始相信，有可能找到可能可约的无障碍构型的不可避免集，而且有问题构型的数量会很少。令他们非常欣慰的是，也已经清楚他们不需要超过环大小14。在1976年的头几个月里，他们继续使用这些棘手构型来指导他们，进一步改进他们的放电方法。

1976年3月，伊利诺伊大学购买了一台强大的新计算机，在春假期间基本闲置，阿佩尔能够有效地利用它来完成检查所有构型可约性的繁重任务。结果这节省了他们许多月的繁琐工作，令他们惊讶的是，任务在6月完成。为了庆祝他们的成功，阿佩尔在数学系的黑板上写了一条便条：

❝

经过仔细检查，看来似乎四种颜色就足够了。（Modulo careful checking it appears that four colors suffice.）

在家人的帮助下，最终检查在几周内完成，产生了1,936个可约构型的不可避免集。1976年7月22日，他们公开宣布，通知了他们的同事，并向该领域的其他工作者发送了预印本。

图23. 证明宣布后数学系的邮戳

[译者注：为何发邮戳？互联网之前，在没有广泛承认的存储列表作为证明的时候，邮戳是一种被广泛承认的版权时间确认方式。需要版权证明的文件可以在邮局装信封盖邮戳，发到另一个可靠地址，让该地址主人不要拆文件再套一层信封盖邮戳发回来。就可以存档了。]

13. 余波

阿佩尔、哈肯和科赫正好及时，因为他们的一些竞争对手正在接近完整的解决方案。杰出的组合学家比尔·塔特认可了他们的解决方案，他们的成功被世界各地的报纸报道。阿佩尔和哈肯为美国数学学会写了一篇简短的"研究公告"，概述了他们证明的主要思想[13]。

[13] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976), no. 5, 711–712, DOI 10.1090/S0002-9904-1976-14122-5. MR424602

1977年12月，阿佩尔和哈肯在《伊利诺伊数学杂志》上发表了一篇关于证明放电部分的长篇论文[14]，并与约翰·科赫合著了关于可约性部分的续篇[15]；这些论文附有提供450页进一步解释和图表的微缩胶片。到那时，作者发现了许多重复和一种构型在另一种构型内的实例，发表列表中的构型数量现在减少到1,482。随后发现的一些错误得到了纠正，但阿佩尔和哈肯知道，由于证明中有如此多的自我纠正，少数异常构型总是可以轻易替换。

[14] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977), no. 3, 429–490. MR543792

[15] K. Appel, W. Haken, and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977), no. 3, 491–567. MR543793

这种计算机辅助证明这样一个长期存在的问题,既受到一部分人的热烈欢迎，也受到一部分人的不安和失望。但也被剩余人的彻底拒绝，他们不接受无法手工检查的数学论证。

图24. 阿佩尔和哈肯的一些可约构型

1986年，阿佩尔和哈肯写了一篇轻松的文章"四色证明足够了"[16]，回答了许多出现的批评，三年后出版了一大卷[17]，纠正了所有检测到的错误，并包括他们微缩胶片页面的打印输出。

[16] K. Appel and W. Haken, The four color proof suffices, Math. Intelligencer 8 (1986), no. 1, 10–20, 58, DOI 10.1007/BF03023914. MR823216

[17] Kenneth Appel and Wolfgang Haken, Every planar map is four colorable, Contemporary Mathematics, vol. 98, American Mathematical Society, Providence, RI, 1989. With the collaboration of J. Koch, DOI 10.1090/conm/098. MR1025335

然后，在1994年，尼尔·罗伯逊（Neil Robertson）和保罗·西摩（Paul Seymour），他们花了许多夏天解决图论中的开放问题，与丹尼尔·桑德斯（Daniel Sanders）和罗宾·托马斯（Robin Thomas）合作，重新设计了阿佩尔-哈肯方法（Appel–Haken approach），使其更加精简和系统化，并获得了仅有633个可约构型的更简单的不可避免集[18]。十年后，他们的方法被法国计算机科学家乔治·贡蒂尔（Georges Gonthier）[19]机器检验，他验证了60,000行形式语言证明，然后宣布他们的证明确实是正确的。四色定理终于可以被认定已证明。

[18] Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1997), no. 1, 2–44, DOI 10.1006/jctb.1997.1750. MR1441258

[19] Georges Gonthier, Formal proof—the four-color theorem, Notices Amer. Math. Soc. 55 (2008), no. 11, 1382–1393. MR2463991