四色定理诞生历程：1852—1976——译自AMS Notices美国数学会通告

★置顶zzllrr小乐公众号（主页右上角）数学科普不迷路！

今年是四色定理诞生50周年。四色问题探讨的是：在平面或球面上绘制的任意地图，是否仅需四种颜色就能对所有区域进行着色，且使任何共享一条公共边界线的两个区域颜色不同。该问题于1852年由弗朗西斯·格思里（Francis Guthrie）首次提出，最终在1976年由肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）解决，此后被正式称为四色定理。

作者：罗宾·威尔逊（Robin Wilson）《美国数学会通告》

AMS Notices

2026-3

译者：zzllrr小乐（数学科普公众号）2026-2-25

作者简介

罗宾·威尔逊（Robin Wilson），英国开放大学纯数学荣誉退休教授、伦敦格雷沙姆学院几何学荣誉退休教授，同时曾任牛津大学基布尔学院研究员。

为纪念这一定理诞生50周年，本文将回溯其证明历程，重点聚焦于参与其中的关键人物。

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

图1 奥古斯塔斯·德摩根（1806-1871）

奥古斯塔斯·德摩根是新成立的伦敦大学学院的首位数学教授。他在数学、逻辑学和哲学领域贡献卓著，以集合论中的“德摩根定律”（De Morgan’s laws）闻名于世。同时，他也是一位多产的通俗数学作家，其著作《悖论集锦》

Budget of Paradoxes

收录了他在当时的文学与科学期刊《雅典娜神庙》

The Athenaeum

上发表的大量文章，于1872年出版。1865年，他当选为伦敦数学会首任主席。

多年来，德摩根与爱尔兰数学家威廉·罗恩·哈密顿（William Rowan Hamilton，又译汉密尔顿）爵士保持通信，分享彼此的近况、数学界的趣闻以及家庭琐事。1852年10月23日，他在给哈密顿的信中写道：

“今天我的一名学生向我询问一个事实的缘由，而我此前并不知道这是一个事实——至今也仍未弄清。他说，若将一个图形任意分割，给各个部分着色，使得任何具有公共边界线的部分颜色不同，那么最多只需四种颜色……我想知道，是否能构造出需要五种或更多颜色的情况……”

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

后来证实，这位“学生”是弗雷德里克·格思里（Frederick Guthrie），他后来成为物理学家，也是伦敦物理学会的创始人。1880年，他在《爱丁堡皇家学会会刊》

Proceedings of Edinburgh’s Royal Society

上发表短文，将这一问题归功于他的兄长弗朗西斯·格思里——弗朗西斯曾是德摩根的学生，在为英格兰地图着色时提出了“四种颜色是否足够为所有地图着色”的疑问。弗朗西斯·格思里最终成为南非的数学教授，同时也是公认的植物学专家；多种植物以他的名字命名，包括石楠花 Erica Guthriei。尽管他此后再未深入研究这一问题，但四色问题有时仍被称为“格思里问题”（Guthrie’s problem）。

图2 弗朗西斯·格思里（1831-1899）

四色问题也曾被错误地归功于德国数学家兼天文学家奥古斯特·莫比乌斯（August Möbius）。1840年，莫比乌斯给学生布置了一道题目：一位垂死的国王将土地遗赠给五个儿子，要求他们将土地分成五个部分，每个部分都与其他四个部分相邻。如果在平面上存在这样五个两两相邻的区域，那么绘制此类地图就需要五种颜色，但证明这种分割不存在，并不能直接证明四色定理——这一误解在该问题的历史上曾多次出现。

德摩根被这个挑战深深吸引，他向亲友和同事询问是否有人已找到解决方案，但始终没有得到明确答案。从一开始，他就错误地认为，证明的关键在于：若地图中存在四个两两相邻的区域，则其中一个区域必然被另外三个区域包围。当他向四元数代数体系的发明者哈密顿提及这一想法时，得到了简洁却恰当的回应：“我不太可能很快尝试你的‘颜色四元数’问题。”

四色问题最早的印刷描述出现在1854年，《雅典娜神庙》期刊的一个专栏中刊登了题为《地图着色》

Tinting Maps

的段落，署名“F. G.”。这可能是弗雷德里克·格思里、弗朗西斯·格思里所写，也可能出自当时正寻求加入伦敦雅典娜神庙俱乐部的地理学家兼博学家弗朗西斯·高尔顿（Francis Galton）之手。

1860年，该期刊再次刊登了一篇由德摩根撰写的匿名书评，提及了这一问题。正是由于这篇书评，四色问题传入美国，引起了查尔斯·桑德斯·皮尔士（Charles Sanders Peirce）的关注。当时皮尔士正在哈佛大学求学，他的父亲本杰明·皮尔士（Benjamin Peirce）是当时美国最杰出的数学家；后来，查尔斯·皮尔士成为著名的逻辑学家和哲学家。这位年轻的学者曾向哈佛数学会提交过一个解决方案，但具体内容已无从考证。

2. 阿瑟·凯莱（Arthur Cayley）

德摩根于1871年去世，至死都未能知晓四色定理是否成立，这一问题似乎也随之被淡忘。但七年后，在伦敦数学会的一次会议上，剑桥数学家阿瑟·凯莱（Arthur Cayley）重新提出了这一问题，使其重获关注。

图3 阿瑟·凯莱（1821-1895）

阿瑟·凯莱出生于伦敦，但早年随经商的父亲在俄罗斯生活。回到英国后，他在伦敦接受教育，17岁时进入剑桥大学三一学院。1840年以优异成绩毕业后，他被任命为学院研究员，但由于需要接受英国国教的圣职，他于1844年离开剑桥，在伦敦的律师学院担任了19年的成功律师。在此期间，他撰写了超过300篇数学论文，并结识了好友兼合作者詹姆斯·约瑟夫·西尔维斯特（James Joseph Sylvester），两人共同开创了代数学的新领域——不变量理论（invariant theory）。1863年，他回到剑桥，担任首任萨德勒（Sadleirian）纯粹数学教授，并在此职位上度过余生。

继德摩根之后，西尔维斯特和凯莱先后担任伦敦数学会主席。1870年代，凯莱开始涉足化学分子计数领域，而西尔维斯特则探索分子与代数不变量之间的潜在联系，并于1878年引入了“图”（graph）一词（即图论意义上的“图”）。

1875年，五年前从伍尔维奇皇家军事学院退休的西尔维斯特，被任命为新成立的巴尔的摩约翰斯·霍普金斯大学的首位数学教授。在那里，他建立了数学研究学派，并协助创办了《美国数学杂志》

American Journal of Mathematics

，该期刊既刊登美国新锐数学家的文章，也收录欧洲知名数学家的研究成果。

1878年6月13日，凯莱出席伦敦数学会会议时，询问四色地图着色问题是否已得到解决。他很快对这一问题产生了浓厚兴趣，并应好友弗朗西斯·高尔顿的邀请，为《皇家地理学会会刊》

Royal Geographical Society’s Proceedings

撰写了一篇题为《论地图着色》

On the colouring of maps

的短文。

在这篇短文中，凯莱承认自己无法找到证明，并试图解释问题的难点所在。更重要的是，他阐明了如何将一般地图的着色问题简化为三次地图（cubic maps）的情况——三次地图指每个交点恰好连接三个区域的地图。对于任何有超过三个区域交汇的地图，只需在该交点处贴上一个“补丁”，即可转化为三次地图（见图4）。如果这个三次地图可以用四种颜色着色，那么将所有补丁缩小为一个点，就能得到原地图的着色方案。这是一项重要进展：此后，地图着色研究者只需专注于三次地图即可。

图4 三次地图的四色问题

（原始地图→添加补丁→着色地图→缩小补丁的示意图）

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

图5 阿尔弗雷德·肯普（1849-1922）

出席1878年6月13日会议的还有阿尔弗雷德·布雷·肯普（Alfred Bray Kempe），他是一名律师，曾是凯莱在三一学院的数学学生。肯普坚信自己能够证明四色定理，经过数月研究，他完成了一篇论文[9]。在时任主编西尔维斯特的邀请下，这篇论文被提交至《美国数学杂志》并正式发表，他还将论文预览版寄给了科学期刊《自然》

Nature

肯普在论文中证明，每个三次地图必定包含至少一个边界边数不超过五的区域——即二边形（digon）、三角形（triangle）、四边形（square）或五边形（pentagon）。这一结论可通过欧拉多面体公式（Euler’s polyhedron formula）推导得出：对于任何具有R个区域、E条边和N个区域交点的平面地图，满足

N - E + R = 2。

若用cₖ表示具有k条边界边的区域数量，则有3N = 2E（因为每条边连接两个交点），因此：

R = c₂ + c₃ + c₄ + c₅ + c₆ + c₇ + c₈ +⋯ ,

2E = 3N = 2c₂ + 3c₃ + 4c₄ + 5c₅ + 6c₆ + 7c₇ + 8c₈ + ⋯

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

4c₂ + 3c₃ + 2c₄ + c₅ - c₇ - 2c₈ - ⋯ = 12

因此，若不存在边界边数不超过五的区域，上式左边将为负数，产生矛盾。

如果地图中包含二边形或三角形，通过数学归纳法可直接证明：先给地图其余部分着色，必然会剩余一种颜色用于给二边形或三角形着色。但如果地图中包含四边形S，它可能被四种颜色（例如按顺序排列的红r、蓝b、绿g、黄y）的区域包围。为解决这种情况，肯普提出了一种有效的颜色交换论证方法，即后来著名的肯普链法（method of Kempe chains）。

图6 肯普链法示意图

肯普观察了与四边形S相邻的红-绿颜色区域（见图6）。如果这些区域没有形成连通链，那么交换其中一部分红-绿颜色，就能为S腾出一种颜色。但如果它们形成了红-绿连通链，交换颜色并不会改善情况。不过在这种情况下，与S相邻的蓝-黄颜色区域会被红-绿链分隔，因此可以交换其中一部分蓝-黄颜色，同样能为S腾出颜色。因此，无论哪种情况，四边形S都能被着色，结论通过归纳法成立。

随后，肯普转向剩余情况——地图中包含五边形P。如果地图其余部分已着色，且五边形P被四种颜色包围（其中一种颜色出现两次），那么通过两次颜色交换，就能消除该颜色的重复出现，从而为P腾出一种颜色，证明即可完成。

这一论证似乎涵盖了所有可能情况，但正如我们后续将发现的，肯普的最后一步存在缺陷，他的证明也成为了数学史上最著名的错误证明之一。

更具价值的是，肯普还提出了另一个重要思想：对地图区域的任何着色方案，都对应着对区域首都的着色（见图7）。若将每对相邻区域的首都用线段连接，就得到了肯普所说的“连接图”（linkage）。此时，四色问题转化为：用四种颜色给这些首都着色，使得任何两个通过线段连接的首都颜色不同。正如我们将看到的，这种将地图区域着色转化为平面图（planar graph）顶点着色的对偶形式，后来成为四色问题的标准表述。

图7 连接图着色示意图

（国家着色→描绘连接图→顶点用颜色字母标记的示意图）

肯普提交论文时，西尔维斯特正在英国夏季旅行，论文由他在约翰斯·霍普金斯大学的同事、期刊联合创始人兼副主编威廉·斯托里（William Story）处理。斯托里未能发现肯普证明中的主要错误，但指出了其中的一些小漏洞，并撰写了一篇题为《对前文的注释》

Note on the preceding paper

的短文，附在肯普的论文之后。斯托里对四色问题的兴趣持续了多年，在肯普的错误被发现后，他与C. S. 皮尔士就该问题进行了通信交流。

与此同时，阿尔弗雷德·肯普发表了多篇关于机械连接装置几何性质的著名论文。凭借这些研究成果以及他所谓的四色问题解决方案，他于1881年当选为伦敦皇家学会会士。后来，他担任该学会的司库，期间资助了一次重要的南极探险，探险队发现的肯普冰川（Kempe glacier）和肯普山（Mount Kempe）便是以他的名字命名的。

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

肯普的“证明”被广泛接受为四色问题的解决方案。但在苏格兰，数学物理学家彼得·格思里·泰特（Peter Guthrie Tait）于1880年在《爱丁堡皇家学会会刊》上发表短文，批评肯普的论证过于复杂，且未能揭示问题的本质。作为回应，泰特提出了几个更简短、更简洁的证明，但均存在缺陷。

图8 彼得·格思里·泰特（1831-1901）

同年晚些时候，泰特提出了一个更具建设性的想法：给三次地图的区域着色（四种颜色），等价于给地图的边界边着色（三种颜色），且每个交点处的三条边颜色各不相同（见图9）。他认为这种替代表述比原始问题更容易证明。尽管这一观点并不正确，但边着色（edge-colorings）后来成为了一个重要的研究课题。

图9 泰特的等价表述示意图

由于肯普的证明被认为是该问题的最终答案，其他数学家也开始对四色问题产生兴趣。牛津大学数学讲师查尔斯·L·道奇森（Charles L. Dodgson）——即著名小说《爱丽丝梦游仙境》的作者刘易斯·卡罗尔（Lewis Carroll）——将其设计成一款双人游戏。布里斯托尔附近的私立学校克利夫顿学院的校长，或许是受到泰特简短“证明”的启发，将四色问题作为学校的挑战题，并规定“解决方案不得超过1页手稿、30行文字和1页图表”。他还将问题寄给《教育期刊》

Journal of Education

，邀请读者尝试解决。伦敦主教弗雷德里克·坦普尔（Frederick Temple）——曾是牛津大学数学讲师，后来成为坎特伯雷大主教——在一次冗长乏味的会议中走神时，找到了一个“解决方案”。但他仅仅证明了平面上不存在五个两两相邻的区域，而正如我们之前所指出的，这并不能证明四色定理。

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

1890年，一篇题为《地图着色定理》

Map-colour theorem

[10]的开创性论文发表，该论文将四色问题的解决推迟了86年。论文作者是珀西·约翰·希伍德（Percy John Heawood），他在牛津大学学习数学期间了解到四色问题。获得牛津学位后，他前往达勒姆学院（后来的达勒姆大学）任教，并在那里度过了余生。希伍德是一位深受爱戴但略显古怪的学者：他每年只在圣诞节那天校准一次手表，若一天没有参加至少一次委员会会议，就认为这一天是“浪费的”。

图10 珀西·希伍德（1861-1955）

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

他在论文中指出，肯普在处理五边形情况时，假设可以同时进行两次颜色交换，但希伍德通过一个具体例子证明了这是不可行的。在他的例子中（见图11），未着色的五边形位于中心，人们可以交换五边形上方区域的红-绿颜色，或交换下方区域的红-黄颜色，但如果同时进行这两次交换，图右侧的绿色区域和黄色区域都会变成红色，这违反了着色规则。

图11 希伍德的反例示意图

幸运的是，希伍德通过改进肯普的论证，证明了每个地图都可以用五种颜色着色——这本身就是一项重要成果。

希伍德还讨论了一个相关问题——帝国问题（empire problem）：每个国家都有一个附属区域（卫星区域），附属区域必须与宗主国颜色相同。他证明了所有此类三次地图都可以用12种颜色着色，并“历经艰辛”找到了一个需要全部12种颜色的具体例子（见图12）。注意，每个由两个区域组成的帝国都与其他所有帝国相邻。

图12 帝国问题示意图

随后，希伍德观察到平面地图与球面地图的着色问题是等价的，并进一步研究了其他可定向曲面上——如带有g个手柄的球面S(g)——三次地图的着色所需颜色数。例如，环面（torus）S(1)上的任何地图都可以用7种颜色着色，希伍德还构造了一个需要全部7种颜色的环面地图。

但希伍德的研究也存在错误。对于可定向曲面S(g)上具有R个区域、E条边和N个交点的三次地图，欧拉公式为N - E + R = 2 - 2g。基于这一公式，希伍德推导出该地图的区域着色所需颜色数为⌊(7 + √(48g + 1))/2⌋，

但对于所有g > 1的情况，他未能证明存在确实需要该数量颜色的地图——这一断言被称为希伍德猜想（Heawood conjecture）。直到1968年，这一猜想才被完整证明[参见2, 3]。

1898年，希伍德发表了第二篇关于四色问题的论文，将其重新表述为数值同余问题。他首先证明，泰特对三次地图边的着色，等价于给每个交点分配数字1或-1，使得每个区域周围的数字之和是3的倍数（见图13）。此外，若交点标记为p₁, p₂, ... , pₙ，则每个区域都对应一个同余式zᵢ + zⱼ + ... + zₖ ≡ 0 (mod 3)，其中每个zᵢ为1或-1，且当交点pᵢ位于该区域的某条边界边上时，zᵢ会出现在同余式中。

图13 希伍德对三次地图交点的标记示意图

在毕生寻求四色定理证明的过程中，希伍德持续探索这一同余关系，最终在90岁时发表了相关论文。

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

希伍德指出肯普证明的缺陷后，肯普试图修正自己的证明，但未能成功。一些数学家甚至开始怀疑四色定理的正确性，丹麦数学家尤利乌斯·彼得森（Julius Petersen）曾表示：

“我无法确定任何事情，但如果要下注，我会坚持认为四色定理是不正确的。”

大约在同一时期，德国数学家赫尔曼·闵可夫斯基（Hermann Minkowki）在哥廷根大学讲授拓扑学（analysis situs）课程。他声称，四色定理之所以未能被证明，是因为只有三流数学家尝试过这一任务，并向学生吹嘘自己能找到证明。随后的几周里，他在课堂上试图证明该定理，但最终未能成功，不得不承认自己也失败了。

20世纪的第一个新想法来自保罗·韦尼克（Paul Wernicke）。他于1866年出生在德国，获得数学学位后，于1893年移民美国并成为美国公民。他在肯塔基州担任现代语言教师，但主要兴趣仍在数学领域，后来返回德国撰写了一篇关于拓扑学的博士论文，之后再次回到美国。

韦尼克长期关注四色问题。在德国期间，他为《数学年刊》

Mathematische Annalen

撰写了一篇重要论文，证明了任何不包含二边形、三角形或四边形的三次地图，不仅必然包含五边形，还必然包含两个相邻的五边形，或一个与六边形相邻的五边形（见图14）。他希望后两种构型能比单纯的五边形更容易研究。

图14 韦尼克的不可避免集示意图

（二边形、三角形、四边形、两个相邻的五边形、五边形与六边形相邻的示意图）

图15 环大小为14的构型示意图

由此，地图中“不可避免集”（unavoidable set）的核心概念应运而生。环大小为k的构型，指的是由k个区域组成的环所包围的一个或多个区域（见图15）；若每个三次地图都必然包含该集合中的至少一个构型，则该集合称为不可避免集。这一概念由肯普提出，经韦尼克发展，成为后来解决四色问题的关键。

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

1912年是四色问题研究的重要一年，两篇具有里程碑意义的论文在美国《数学年刊》

Annals of Mathematics

上发表，作者分别是奥斯瓦尔德·维布伦（Oswald Veblen）和乔治·伯克霍夫（George Birkhoff）。加之伯克霍夫在次年发表的一篇开创性论文，四色问题的研究进入了新的发展阶段。

图16 奥斯瓦尔德·维布伦（1880-1960）

奥斯瓦尔德·维布伦出生于爱荷华州，14岁进入爱荷华大学，后转入哈佛大学，最终在芝加哥大学获得几何学博士学位——几何学也是他最具代表性的研究领域。1905年至1932年，他在普林斯顿大学任教，之后成为新成立的高等研究院（IAS）的首位数学教授。

在题为《模方程在拓扑学中的应用》

An application of modular equations in analytic situs

的论文中，维布伦运用几何学和代数学思想来研究四色问题。他首先引入两个矩阵来描述具有给定顶点（交点）、边界边和区域标记的地图：点-边关联矩阵（vertex–edge incidence matrix）A，其中第(i,j)项为1当且仅当顶点i位于边j上，否则为0；边-区域关联矩阵（edge–region incidence matrix）B，其中第(i,j)项为1当且仅当边i与区域j相邻，否则为0。

每个矩阵都对应两组线性方程组；例如，对于矩阵B，方程组中的变量代表地图的区域，每条边对应一个形式为yₐ + yb = 0的方程，其中yₐ和yb代表沿该边相邻的两个区域。维布伦将四元有限域（finite field）中的元素作为四种颜色，证明了四色问题的解等价于找到一组满足所有上述方程的变量值{yᵢ}。

维布伦进一步发展了这些思想，将四色问题表述为有限射影空间（finite projective space）的子空间问题。他还证明了由矩阵A导出的一组方程组，与我们之前提到的希伍德同余式是等价的。

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

1912年初，维布伦在普林斯顿大学的好友兼同代人乔治·戴维·伯克霍夫（George David Birkhoff），成为20世纪早期最具影响力的全能数学家之一。他出生于密歇根州，早年就展现出非凡的数学天赋。1902年，他进入芝加哥大学，与维布伦首次相遇。在芝加哥大学学习一年后，他转入哈佛大学攻读学士和硕士学位，随后返回芝加哥大学，撰写了关于微分方程的博士论文。在威斯康星大学任教两年后，他转入普林斯顿大学并晋升为教授，1912年回到哈佛大学，此后一直在该校任教直至去世。

图17 乔治·伯克霍夫（1884-1944）

尽管伯克霍夫最著名的研究领域是动力系统、微分方程和遍历理论等，但他毕生都对四色问题充满兴趣。为了寻求证明，他常常让妻子绘制复杂的地图供自己着色。

伯克霍夫研究地图着色的第一个方法是定量分析：计算用k种颜色给给定地图着色的方式数P(k)。例如，对于四个两两相邻的区域组成的地图，有：

P(k) = k(k - 1)(k - 2)(k - 3)

= k⁴ - 6k³ + 11k² - 6k

他证明了P(k)始终是k的多项式（现称为地图的(染、着、涂)色多项式，chromatic polynomial），并指出：若地图有n个区域和m条边，则P(k)的首项为kⁿ - mkⁿ⁻¹，同时给出了其他所有系数的计算公式。他希望通过对这些多项式的一般研究，证明所有地图都满足P(4) > 0（即存在四种颜色的着色方案）。

伯克霍夫对色多项式的兴趣贯穿一生，分别于1930年和1934年发表了相关论文。1930年的论文由哈斯勒·惠特尼（Hassler Whitney）整理——惠特尼后来成为拓扑学先驱，他关于四色问题的想法给伯克霍夫留下了深刻印象，并在伯克霍夫的指导下完成了题为《图的着色》

The Coloring of Graphs

的博士论文；惠特尼还发表了一篇关于色多项式的著名论文，提出了一种更简洁的系数计算方法，并证明了这些系数的符号始终交替变化。伯克霍夫去世后，与他的前研究生丹尼尔·C·刘易斯（Daniel C. Lewis）合作撰写的一篇关于色多项式的长篇影响论文正式发表。

1913年，伯克霍夫在一篇开创性论文[11]中，为四色定理的最终解决做出了重要贡献：他将“可约构型”（reducible configuration）定义为：若包围该构型的环区域的所有着色方案，都能扩展到构型内部的区域，则该构型为可约构型。由此可知，可约构型不可能出现在四色定理的最小反例中。

伯克霍夫系统地证明了：所有环大小为3或4的构型都是可约的；对于环大小为5的构型，除了单个五边形外，其余都是可约的。

他还证明了由四个五边形组成、被环大小为6的区域包围的伯克霍夫菱形（Birkhoff diamond）是可约的（见图18）。该构型的环区域共有31种本质不同的着色方案：其中16种可直接扩展到内部的五边形，其余15种需通过一次或多次肯普颜色交换才能扩展。

图18 伯克霍夫菱形示意图

在随后的几十年里，更多的可约构型被发现，数量最终达到数千种。

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

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

与此同时，美国数学家菲利普·弗兰克林（Philip Franklin）开始涉足这一领域。他毕业于纽约城市学院，后转入普林斯顿大学，在奥斯瓦尔德·维布伦的指导下完成了题为《四色定理》

The Four Color Theorem

的博士论文。随后，他发表了一篇重要论文[12]，扩展了关于不可避免集和可约构型的现有知识。1924年，他加入麻省理工学院，此后一直在该校任教，研究领域广泛，并撰写了多部广受好评的学生教材。

弗兰克林在论文中利用肯普的计数公式，发现了更多可约构型，例如与三个五边形相邻的五边形、与四个五边形和两个六边形相邻的六边形等。他还证明了：任何不包含二边形、三角形或四边形的地图，都必然包含以下三种构型之一：与两个其他五边形相邻的五边形、与两个五边形和一个六边形相邻的五边形、与一个五边形和两个六边形相邻的五边形——这一结论给出了新的不可避免集（见图19）。此后，直到1940年，以勒贝格积分闻名的亨利·勒贝格（Henri Lebesgue）在其最后一篇论文中提出了多个新的不可避免集，这一领域才再添新成果。

图19 弗兰克林的不可避免集示意图

（二边形、三角形、四边形、三个相邻的五边形、

两个五边形与一个六边形相邻、一个五边形与两个六边形相邻的示意图）

弗兰克林还推导出：所有区域数不超过25的地图都可以用四种颜色着色。西弗吉尼亚大学的克拉伦斯·雷诺兹（Clarence Reynolds）进一步将这一数字提高到27，而C. E. 温（C. E. Winn）于1940年将其提升至35。

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

第二次世界大战后，四色定理的证明尝试迎来了新的转折，德国数学家海因里希·黑施（Heinrich Heesch）的出现推动了研究方向的转变。他出生于基尔，在慕尼黑同时获得数学和音乐学位，后在苏黎世大学完成了关于几何公理的博士论文。随后，他转入哥廷根大学，担任赫尔曼·外尔（Hermann Weyl）的助手，从事晶体研究。期间，他因解决了平面镶嵌图案中的“正镶嵌问题”（regular parquet problem）而声名鹊起——这一问题是大卫·希尔伯特（David Hilbert）1900年在巴黎国际数学家大会上发表著名演讲时提出的“第18问题”的一部分。

但自1933年起，纳粹对德国大学教职人员的清洗使得学术环境日益恶劣，黑施辞去了哥廷根大学的职位，返回基尔与父母同住。在随后的12年里，他以教书为生，同时继续研究镶嵌图案；其中一种图案后来被应用于哥廷根大学图书馆的天花板设计。

黑施于20世纪30年代中期首次了解到四色问题，并对其产生了毕生的兴趣。他很快意识到，解决这一问题的关键在于找到一个“不可避免的可约构型集”——“不可避免”意味着每个地图都必须包含该集合中的至少一个构型；“可约”意味着无论包含哪个构型，地图其余部分的所有着色方案都能扩展到该构型。换句话说，由于不可避免集中的可约构型不可能出现在四色定理的最小反例中，因此这样的反例不存在，四色定理成立。

1948年左右，黑施在基尔向大量听众发表了关于四色问题的演讲。他提出，需要找到一个有限的不可避免可约构型集，且该集合可能非常大——可能包含多达10000个构型。为了便于分类，他将构型定义为D-可约（D-reducible）：若包围构型的环区域的所有着色方案，都能通过直接着色或颜色交换扩展到构型内部，则该构型为D-可约。正如我们之前所见，二边形、三角形、四边形和伯克霍夫菱形都是D-可约的。他还将通过某种修改后可变为可约构型的构型称为C-可约（C-reducible）。

与此同时，黑施构造了大量可约构型，多年来培养出了一眼就能判断构型是否可约的能力——准确率最终超过80%。为此，他指出了三种会阻碍构型可约性的特征：“四腿区域”（4-legger region）——与环区域中四个连续区域相邻；“三腿铰接区域”（3-legger articulation region）——与环区域中三个非全部相邻的区域相邻；“悬挂5-5对”（hanging 5-5 pair）——两个相邻的五边形，且均与环内部的同一个区域相邻（见图20）。

图20 阻碍可约性的三种特征示意图

（四腿区域、三腿铰接区域、悬挂5-5对的示意图）

如前所述，当时已知的不可避免集数量很少，但黑施发现了一种证明给定构型集为不可避免集的有效方法——放电法（method of discharging）。该方法有多种形式，为了说明其基本思想，我们可以证明韦尼克的构型集（见图14）是不可避免集：

假设存在一个不包含二边形、三角形、四边形、两个相邻的五边形以及五边形与六边形相邻构型的地图——那么每个五边形只能与边数不少于七的区域相邻。给每个k边形区域分配一个“电荷”：6-k，则五边形的电荷为1（单位电荷），六边形的电荷为0，边数超过六的多边形电荷为负。根据肯普的计数公式，整个地图的总电荷为12（正数）。若通过“放电”过程，将每个五边形的单位电荷平均分配给其五个相邻区域，则地图的总电荷仍为正数，但此时每个五边形的电荷变为0，六边形的电荷仍为0，而其他区域获得的电荷不足以使其变为正数——这导致总电荷非正，产生矛盾。因此，假设不成立，韦尼克的构型集是不可避免集。

此时，图论学科正在发展，大多数地图着色研究者开始采用四色问题的“对偶形式”——即肯普的连接图形式：不再给地图区域着色（相邻区域颜色不同），而是给平面图的顶点着色，使得任何两个相邻顶点颜色不同。为此，黑施引入了对应于五边形、六边形等区域的顶点符号（见图21），这些符号后来被广泛采用。

图21 黑施的地图区域符号示意图

（五边形、六边形、七边形、八边形的符号及组合示意图）

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

沃尔夫冈·哈肯（Wolfgang Haken）于1928年出生在柏林，早年就对数学表现出浓厚兴趣。15岁时，他被征召加入二战防空部队，同时继续完成学业，并于1946年初毕业。当时，大多数德国大学不招收23岁以下的学生，但基尔大学是个例外，17岁的哈肯成为该校最年轻的学生。他在学年中期被录取，攻读数学、物理和哲学专业，直接进入第二学期的课程学习，没有任何前期基础，但他最终成功跟上了进度，并在后来将这一时期描述为“非常、非常令人兴奋——对我来说，那是一段美好的时光”。

当时基尔大学只有一位活跃的数学教授——卡尔-海因里希·魏斯（Karl-Heinrich Weise）。魏斯是一位优秀的教师，1947年在拓扑学课程中，他提到了三个未解决的问题：结问题（knot problem）、庞加莱猜想（Poincaré conjecture）和四色问题。这三个问题后来都成为哈肯毕生研究的重要部分：他解决了结问题，为庞加莱猜想的研究做出了重大贡献，并最终与肯尼斯·阿佩尔共同解决了四色问题。

在基尔大学，哈肯结识了海因里希·黑施，并参加了他关于四色问题的演讲。当时哈肯对此理解不深，但后来回忆起，黑施提到需要系统研究约10000个特殊情况才能证明四色定理。这次演讲在哈肯心中埋下了种子，并在数十年后开花结果。

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

在慕尼黑期间，哈肯始终保持着对数学的兴趣，尤其对“结问题”——判断给定的三维闭合曲线（如缠绕的绳子）是否打结——着迷。他利用业余时间研究这一问题，最终成功找到完整解决方案，并在1954年阿姆斯特丹国际数学家大会上宣布了这一成果。他面临的困难是，在全职工作的同时，难以抽出时间撰写完整的证明论文，但最终他还是完成了这项工作，其长篇证明发表在《数学学报》

Acta Mathematica

上。

伊利诺伊大学厄巴纳-尚佩恩分校的逻辑学家比尔·布恩（Bill Boone）阅读了哈肯的证明后，深受触动，邀请他担任该校的客座教授。在那里，哈肯就其打结问题的解决方案发表了演讲。随后，他在普林斯顿高等研究院工作了两年，之后返回伊利诺伊大学，担任终身教授。

哈肯随后将注意力转向证明庞加莱猜想。他处理难题的方法是：将问题视为一棵有许多枝叶的树，逐一剪除枝叶，直至整棵树被摧毁。对于庞加莱猜想，他找到了200个需要“剪除”的“枝叶”，并声称已剪除了198个，但在与最后两个“枝叶”抗争了十年后，他最终承认失败。

1967年，奥伊斯坦·奥尔（Oystein Ore）出版了关于四色问题的第一部专著[6]，同年，哈肯将注意力重新投向了这个二十年来未曾关注的问题。他首先联系黑施，询问他是否已解决四色问题，或是仍在研究那10000个特殊情况。此时，黑施已构造出数千个可约构型，但未能将它们整合为一个不可避免集。

哈肯邀请黑施到伊利诺伊大学发表关于四色问题的演讲，并询问他日益普及的计算机是否能帮助验证如此多的构型。当时黑施在汉诺威自由大学工作，已聘请前研究生卡尔·迪尔（Karl Dürre）在该校的计算机上测试构型的D-可约性——对于任何给定构型，通过检查包围环区域的所有着色方案是否能直接或通过颜色交换扩展到内部区域，即可完成验证。

如前所述，对于环大小为6的伯克霍夫菱形，需要检查31种不同的环区域着色方案。但随着构型复杂度的增加，着色方案的数量会急剧增长——环大小每增加1，着色方案数量就会变为原来的4倍；对于环大小为14的构型，需要考虑的着色方案多达199271种。由于需要验证的构型数量众多，当时的计算机需要数千小时才能完成，这在当时看来是难以实现的。

伊利诺伊大学没有可用的计算机，但该校计算机系设法安排黑施和迪尔使用长岛布鲁克海文国家实验室的大型Cray计算机。实验室主任岛本（Yoshio Shimamoto）本人也对四色问题着迷，邀请他们在布鲁克海文实验室长期工作。当时已得知，任何解决方案都必然涉及环大小不小于12的构型，而Cray计算机使他们能够验证许多环大小为13的构型的D-可约性，并开始着手处理环大小为14的构型。

在研究过程中，岛本发现了一个环大小为14的单一构型——所谓的“岛本马蹄形”（Shimamoto horseshoe），若该构型被证明是D-可约的，将直接证明四色定理。这一消息迅速传遍全球，但经过26小时的连续计算，计算机最终证实该马蹄形构型并非D-可约，令所有人失望不已。

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

1970年左右，黑施开发了一些新的放电过程，他认为这些过程可将四色问题简化为8900个难以处理的构型（环大小最大为18），只需逐一验证这些构型即可。但此时，哈肯对需要处理如此多复杂情况的前景感到失望，在伊利诺伊大学的一次演讲中，他宣布：

“计算机专家告诉我，这样的研究方式是不可行的。现在，我决定放弃。我认为，这是无需计算机就能达到的极限。”

出席这次演讲的有肯尼斯·阿佩尔（Kenneth Appel），他在密歇根大学完成了关于数理逻辑与代数学关联的博士论文。阿佩尔是一位技艺高超的计算机程序员，在密歇根大学期间学会了编程技能，职业生涯中曾任职于道格拉斯飞机公司，并在普林斯顿国防分析研究所从事研究，1961年转入伊利诺伊大学。

演讲时，阿佩尔正担任哈肯一名研究生的博士论文评审，该论文涉及四色问题的一个方面。在哈肯宣布放弃后，阿佩尔向他提出了一个建议：

“我认为没有什么是计算机做不到的——有些事情只是需要更长时间而已。我们为什么不试一试呢？”

图22 肯尼斯·阿佩尔（1932—2013）与沃尔夫冈·哈肯（1928—2022）

在此之前，大多数地图着色研究者都是先寻找大量可约构型，再试图将它们整合为不可避免集，但均以失败告终。而哈肯的方法则不同：他先构建由“可能可约”的构型组成的不可避免集，再验证这些构型的可约性；对于无法轻易证明为可约的构型，则用其他构型替代。他希望通过这种迭代过程，更快地找到不可避免的可约构型集。

当阿佩尔和哈肯开始实践这一想法时，计算机输出的构型列表中存在大量重复项，但阿佩尔很快引入了一些简单的修改，减少了重复。这迅速成为一个持续的实验过程：阿佩尔和哈肯定期调整放电算法，改进计算机程序，以优化构型列表。

为简化问题，他们将研究范围限制在不包含黑施提出的三种可约性障碍的构型上，因为这些构型不太可能出现在最终的不可避免集中。起初，他们专注于仅排除前两种障碍（四腿区域和三腿铰接区域）的“地理良好”构型，并认为在几个月内构建出此类构型的不可避免集是可行的。基于这一想法，他们在1974年花费了数月时间，通过理论论证证实了此类不可避免集的存在，并提出了可实现的构造方法。

渐渐地，阿佩尔和哈肯意识到，尽管D-可约构型通常易于处理（若规模不太大），但C-可约构型需要进行修改，且修改方式尚不明确，因此需要外界帮助。阿佩尔联系了该校计算机科学系，发现研究生约翰·科赫（John Koch）愿意提供帮助。阿佩尔委托他寻找修改环大小为11的C-可约构型的简单方法，科赫成功完成了这一任务，随后阿佩尔将科赫的方法扩展到更大环的构型。

1975年，阿佩尔和哈肯引入了黑施提出的第三种可约性障碍（悬挂5-5对），并欣慰地发现，这一修改仅使不可避免集的规模增加了一倍。在接下来的几个月里，他们持续改进方法，最终形成了一种“人机对话”模式——计算机似乎能自主发现改进方案，优化了预设程序。

此时，他们已确信能够找到一个无障碍、且构型大概率可约的不可避免集，且问题构型的数量会很少。令他们感到宽慰的是，研究表明无需处理环大小超过14的构型。1976年上半年，他们继续改进放电方法，并以这些复杂构型为指导，完善研究方案。

1976年3月，伊利诺伊大学购置了一台功能强大的新计算机，春假期间该计算机基本闲置，阿佩尔得以利用它高效完成构型可约性的大规模验证工作。这一举措为他们节省了数月的繁琐劳动，令他们惊喜的是，验证工作于6月完成。为庆祝这一成果，阿佩尔在数学系的黑板上写下：

“经仔细验证，四种颜色足够。”（Modulo careful checking it appears that four colors suffice.）

在家人的帮助下，最终验证工作在几周内完成，形成了包含1936个可约构型的不可避免集。1976年7月22日，他们正式公布了这一结果，告知同事，并向该领域的其他研究者发送了预印本。

图23 证明公布后数学系的邮戳示意图

（印有“四种颜色足够”（FOUR COLORS SUFFICE）字样的邮戳）

13. 后续发展

阿佩尔、哈肯和科赫的研究恰逢其时——当时一些竞争对手也即将完成解决方案。著名组合数学家比尔·塔特（Bill Tutte）认可了他们的成果，他们的成功被全球报纸报道。阿佩尔和哈肯为美国数学会撰写了一篇简短的“研究公告”[13]，概述了证明的核心思想。

1977年12月，阿佩尔和哈肯在《伊利诺伊数学期刊》

Illinois Journal of Mathematics

上发表了关于证明中放电过程的长篇论文[14]，并与约翰·科赫合作发表了关于可约性的后续论文[15]；这些论文附带了一张包含450页详细解释和图表的缩微胶片。此时，作者们已发现列表中存在许多重复构型和包含关系，出版的构型列表被缩减至1482个。随后发现的一些错误也得到了修正，但阿佩尔和哈肯知道，由于证明本身具有很强的自我修正能力，少数有问题的构型总能被轻易替换。

这一长期悬而未决的问题，最终通过计算机辅助证明得以解决——这一成果令一些人欢欣鼓舞，也让许多人感到不安和失望，还有一部分人则完全拒绝接受这种无法手动验证的数学论证。

图24 阿佩尔和哈肯的部分可约构型示意图

1986年，阿佩尔和哈肯发表了一篇轻松的文章《四色证明已足够》

The four color proof suffices

[16]，回应了诸多批评；三年后，他们出版了一部大部头著作[17]，修正了所有已发现的错误，并收录了缩微胶片的打印版。

1994年，尼尔·罗伯逊（Neil Robertson）、保罗·西摩（Paul Seymour）、丹尼尔·桑德斯（Daniel Sanders）和罗宾·托马斯（Robin Thomas）合作，重新优化了阿佩尔-哈肯的证明方法，使其更简洁、系统，并得到了一个仅包含633个可约构型的更简单不可避免集[18]——罗伯逊和西摩多年来一直利用暑期时间解决图论中的开放问题。十年后，法国计算机科学家乔治·贡蒂埃（Georges Gonthier）[19]对他们的方法进行了完整的机器验证，核实了60000行形式语言证明，最终宣布该证明完全正确。至此，四色定理终于被认为得到了彻底证明。

参考文献[1-8]包含了关于四色定理历史和证明的更多信息，以及本文引用论文的详细参考文献。参考文献[9-12, 18-19]是本文提及的著名论文，[13-17]是阿佩尔和哈肯的相关著作。

原文参考文献

[1] Robin Wilson, Four colors suffice: How the map problem was solved, Princeton Science Library, Princeton University Press, Princeton, NJ, 2014. Revised color edition of the 2002 original, with a new foreword by Ian Stewart. MR3235839.

[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.

[4] Donald MacKenzie, Slaying the Kraken: the sociohistory of a mathematical proof, Soc. Stud. Sci. 29 (1999), no. 1, 7–60, DOI 10.1177/030631299029001002. MR1692830.

[5] Rudolf Fritsch and Gerda Fritsch, The four-color theorem: History, topological foundations, and idea of proof, Springer-Verlag, New York, 1998. Translated from the 1994 German original by Julie Peschke, DOI 10.1007/978-1-4612-1720-6. MR1633950.

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

[7] Thomas L. Saaty and Paul C. Kainen, The four-color problem: Assaults and conquest, McGraw-Hill International Book Co., New York-Bogotá-Auckland, 1977. MR480047.

[8] Hans-Günther Bigalke, Heinrich Heesch (German), Vita Mathematica, vol. 3, Birkhäuser Verlag, Basel, 1988. Kristallgeometrie. Parkettierungen. Vierfarbenforschung. [Geometry of crystals. Tilings. Four color problem], DOI 10.1007/978-3-0348-7246-1. MR946224.

[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.

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

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

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

[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.

[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.

[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.

[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

参考资料

https://www.ams.org/journals/notices/202603/noti3305/noti3305.html

小乐数学科普近期文章

·开放 · 友好 · 多元 · 普适 · 守拙·

让数学

更加

易学易练

易教易研

易赏易玩

易见易得

易传易及

欢迎评论、点赞、在看、在听

收藏、分享、转载、投稿

查看原始文章出处

点击zzllrr小乐

公众号主页

右上角

置顶加星★

数学科普不迷路！