The Four-Color Theorem Gets a Rare New Proof

The four-color theorem is simple to state: Given a contiguous map, is it possible to color each region with one of four colors such that no neighboring regions share a color?

四色定理很容易表述：给定一个连续的地图，是否可以用四种颜色中的一种对每个区域进行着色，使得没有相邻区域共享颜色？

Some math problems continue to haunt researchers long after they’ve been solved.

有些数学问题在解决后很长一段时间内仍然困扰着研究人员。

A proof emerges, is even celebrated, and yet dissatisfaction lingers.

证据出现，甚至受到庆祝，但不满情绪依然存在。

Perhaps the argument is too convoluted — the hunt persists for the elusive one-page paper — or perhaps it fails to give a deeper theoretical insight into why something is true.

也许这个论点太复杂了——对难以捉摸的一页论文的追寻仍在继续——或者也许它未能对为什么某件事是真实的提供更深入的理论见解。

Whatever the reason, mathematicians return, again and again, to a case that is otherwise considered closed.

不管出于什么原因，数学家们一次又一次地回到一个被认为已经结束的案例。

One of the most famous such cases is that of the four-color theorem, a problem that transformed how mathematicians think about their subject.

最著名的案例之一是四色定理，这个问题改变了数学家对其学科的思考方式。

The problem is simple to state, and even simpler to see: Given a contiguous map, is it possible to color each region with one of four colors such that no neighboring regions share a color?

这个问题很容易表述，甚至更容易理解：给定一个连续的地图，是否可以用四种颜色之一对每个区域进行着色，使得相邻区域没有共享颜色？

In the mid-19th century, the question was of trifling interest to mapmakers, who had far more than four colors at their disposal and saw no particular reason to restrict their palette.

在 19 世纪中叶，地图制作者对这个问题兴趣不大，他们可以使用的颜色远不止四种，而且没有特别的理由限制他们的调色板。

But to mathematicians, both amateur and professional, the brain teaser quickly turned into an obsession.

但对于业余和专业数学家来说，这个脑筋急转弯很快就变成了一种痴迷。

In the mid-19th century, a brain teaser about map colors quickly turned into an obsession.

19 世纪中叶，关于地图颜色的脑筋急转弯很快就变成了一种痴迷。

Today, the hunt is still on for a simpler solution to the deceptively tricky problem.

如今，人们仍在寻找一种更简单的解决方案来解决这个看似棘手的问题。

The first purported proof , announced in 1879, stood for 11 years before it was proved incorrect.

第一个所谓的证据于 1879 年公布，在被证明是错误的之前已经存在了 11 年。

More wrong answers would follow, from lawyers and doctors and famous graph theorists, too.

更多错误的答案也随之而来，来自律师、医生和著名的图论学家。

“Here we have a problem that even a child can understand,” said Carsten Thomassen , a graph theorist at the Technical University of Denmark.

“我们遇到了一个连孩子都能理解的问题，”丹麦技术大学的图论学家卡斯滕·托马森 (Carsten Thomassen) 说。

“I think that’s the reason why it has been such a big challenge.”

“我认为这就是为什么它是一个如此巨大的挑战的原因。”

The theorem was finally proved nearly a century later — but with computer methods that were considered scandalous at the time, causing mathematicians to question what they considered a proof in the first place.

近一个世纪后，这个定理终于被证明了——但当时的计算机方法被认为是可耻的，这让数学家们质疑他们最初认为的证明是什么。

The status of the problem remained a source of debate until 1997, when the use of computers became more common and a simpler computer-assisted proof was found.

这个问题的现状一直是争论的焦点，直到 1997 年，计算机的使用变得更加普遍，并且发现了更简单的计算机辅助证明。

Yet even today, the “four-color disease,” as Mikkel Thorup , a computer scientist at the University of Copenhagen, puts it, continues to circulate.

然而，即使在今天，正如哥本哈根大学计算机科学家米克尔·索鲁普 (Mikkel Thorup) 所说，“四色病”仍在继续流行。

He and Thomassen count themselves among the afflicted.

他和托马森认为自己是受苦受难的人之一。

For such a simple statement, there must be a simpler reason why it is true.

对于这样一个简单的说法，一定有一个更简单的理由来证明它是正确的。

Or at least a more efficient way to demonstrate it.

或者至少是一种更有效的展示方式。

After nearly a decade of work, Thorup, Thomassen, and four colleagues in Denmark, Canada, and Japan have produced yet another computer proof of the theorem.

经过近十年的工作，索鲁普、托马森和丹麦、加拿大和日本的四位同事又给出了该定理的另一个计算机证明。

From left: Carsten Thomassen, Ken-ichi Kawarabayashi, Mikkel Thorup, and Bojan Mohar are part of a team that recently re-proved the four-color theorem, revealing in the process a more efficient way to color maps and graphs.

左起：Carsten Thomassen、Ken-ichi Kawarabayashi、Mikkel Thorup 和 Bojan Mohar 所在的团队最近重新证明了四色定理，在此过程中揭示了一种更有效的为地图和图表着色的方法。

The proof — which was posted online in March 2026 and will be presented in November at the annual Foundations of Computer Science conference — is in some ways even more complicated than its predecessors.

该证明于 2026 年 3 月在网上发布，并将于 11 月在年度计算机科学基础会议上提出，在某些方面甚至比其前身更加复杂。

“It looks like they’ve used electricity liberally in actually carrying out their proof,” said Georges Gonthier, a computer scientist at Inria in Paris.

巴黎 Inria 的计算机科学家 Georges Gonthier 表示：“看起来他们在实际证明过程中大量使用了电力。”

But in the process of crafting their argument, the researchers provided a far more efficient way to color maps.

但在阐述他们的论点的过程中，研究人员提供了一种更有效的彩色地图方法。

And in doing so, they uncovered new insights into structural properties of important mathematical objects called planar graphs — opening up the potential for progress on many other stubborn problems in graph theory.

在此过程中，他们发现了对平面图这一重要数学对象的结构特性的新见解，为解决图论中许多其他顽固问题开辟了可能。

Given the problem’s history of false starts and dashed hopes, Gonthier said, “it’s really cool to see a real result for once.”

贡蒂尔说，考虑到这个问题的错误开始和希望破灭的历史，“能看到一次真正的结果真是太酷了。”

In 1852, the mathematician Francis Guthrie was coloring in a map of English counties when he noticed that he needed only four colors.

1852 年，数学家弗朗西斯·格思里 (Francis Guthrie) 在给英国郡地图着色时，发现他只需要四种颜色。

Was this always true, he wondered?

他想知道，这总是真的吗？

He asked his brother Frederick, also a mathematician, whose adviser, Augustus De Morgan, took an interest in the question and decided to market it to a wider audience.

他问了他的兄弟弗雷德里克（Frederick），他也是一名数学家，他的顾问奥古斯都·德·摩根（Augustus De Morgan）对这个问题感兴趣，并决定向更广泛的受众推销它。

In 1879, when a mathematician named Alfred Bray Kempe claimed to have a solution, a press release announced the achievement in Nature.

1879 年，当一位名叫阿尔弗雷德·布雷·肯佩 (Alfred Bray Kempe) 的数学家声称找到了解决方案时，《自然》杂志上的一份新闻稿宣布了这一成就。

Kempe started by assuming the opposite of what he wanted to prove: that there is a map that can’t be colored with only four colors.

肯普首先假设了与他想要证明的相反的情况：存在一张地图不能只用四种颜色来着色。

He then sought to show that this assumption would ultimately lead to a contradiction — meaning that no such map could exist.

然后他试图证明这一假设最终会导致矛盾——这意味着这样的地图不可能存在。

In that case, all maps would have to be four-colorable.

在这种情况下，所有地图都必须是四色的。

First, he said, imagine that the non-four-colorable map from your assumption is as “minimal” as possible: If you were to remove any country from it, the remaining map would be four-colorable.

他说，首先，想象一下你的假设中的非四色地图尽可能“最小”：如果你要从中删除任何国家，剩下的地图将是四色的。

Next, do away with geography and other extraneous details by redrawing your map as what’s known as a planar graph.

接下来，通过将地图重新​​绘制为所谓的平面图来消除地理和其他无关的细节。

Represent each country as a point (or vertex), and draw a line (or edge) between two points if those countries share a border.

将每个国家/地区表示为一个点（或顶点），如果这些国家/地区共享边界，则在两点之间绘制一条线（或边缘）。

Your map-coloring problem is now a graph-coloring one, opening it up to the tools of graph theory.

你的地图着色问题现在是一个图形着色问题，向图论工具开放了它。

In particular, in the 18th century, the Swiss mathematician Leonhard Euler discovered that planar graphs have many useful properties — among them a guarantee that any such graph will contain at least one vertex with five or fewer neighbors.

特别是，在 18 世纪，瑞士数学家 Leonhard Euler 发现平面图具有许多有用的属性 - 其中保证任何此类图都将包含至少一个具有五个或更少邻居的顶点。

That means that your graph must have at least one of these six configurations, what Kempe called an unavoidable set:

这意味着您的图表必须至少具有以下六种配置中的一种，Kempe 称之为不可避免的集合：

And because your graph is minimal, if you remove any of these configurations from it, you’ll be left with a graph that can be recolored with four colors.

而且因为您的图表很小，所以如果您从中删除任何这些配置，您将留下一个可以用四种颜色重新着色的图表。

Kempe’s genius move was to show that no matter which of these configurations you remove, you can always find a way to swap the graph’s colors around so that when you add your missing vertex back, it’s possible to color all the vertices without needing a fifth color.

肯普的天才之举是表明，无论您删除其中哪一个配置，您总能找到一种方法来交换图形的颜色，这样当您将丢失的顶点添加回来时，就可以为所有顶点着色，而无需第五种颜色。

By showing that each unavoidable configuration is “reducible” in this way, you’ve demonstrated that your minimal graph is four-colorable after all — your original assumption was wrong.

通过以这种方式表明每个不可避免的配置都是“可简化的”，您已经证明了您的最小图毕竟是四色的 - 您最初的假设是错误的。

The four-color theorem must be true.

四色定理必定成立。

Unfortunately, 11 years after Kempe announced his proof, the mathematician Percy John Heawood discovered a subtle flaw in his color-swapping procedure: In the case where the vertex you remove has five neighbors, Kempe’s method could lead to the same colors ending up next to one another.

不幸的是，在肯普宣布他的证明 11 年后，数学家珀西·约翰·希伍德在他的颜色交换过程中发现了一个微妙的缺陷：在您删除的顶点有五个邻居的情况下，肯普的方法可能会导致相同的颜色最终彼此相邻。

Heawood was initially reluctant to report the error, in part because Kempe’s approach was so elegant.

希伍德最初不愿意报告这个错误，部分原因是肯佩的方法非常优雅。

And indeed, despite Kempe’s error, his swapping procedure — today known as a Kempe chain — would remain at the core of future solutions to the problem.

事实上，尽管肯佩犯了错误，他的交换程序——今天被称为肯佩链——仍将是未来问题解决方案的核心。

“Isn’t it interesting that you make a mistake which is so interesting that it’s named after you?” Thomassen said.

“你犯了一个如此有趣以至于以你的名字命名的错误，这不是很有趣吗？”托马森说道。

In the end, no one was able to show that the last configuration in Kempe’s unavoidable set was reducible.

最终，没有人能够证明肯普不可避免的集合中的最后一个配置是可约化的。

It turned out that a correct proof would instead require identifying a much larger, more complicated set of 8,900 configurations — and showing that all of them are reducible.

事实证明，正确的证明需要识别一组更大、更复杂的 8,900 种配置，并证明所有配置都是可简化的。

The task was impossible to deal with by hand.

这项任务不可能靠手工来完成。

It needed computers.

它需要计算机。

In 1976, the mathematicians Kenneth Appel and Wolfgang Haken figured out a clever way to lower the number of possibilities first to 1,936 configurations, and then to 1,482.

1976 年，数学家 Kenneth Appel 和 Wolfgang Haken 找到了一种巧妙的方法，将可能性的数量首先降低到 1,936 种配置，然后降低到 1,482 种。

They then used the supercomputers at the University of Illinois to properly reduce each one.

然后他们使用伊利诺伊大学的超级计算机来适当减少每一个。

At last, they said, the four-color theorem was settled.

他们说，四色定理终于得到解决。

The British mathematician Augustus De Morgan sought to stir up broader interest in the four-color problem.

英国数学家奥古斯塔斯·德·摩根试图激起人们对四色问题更广泛的兴趣。

“A student of mine asked me today to give him a reason for a fact which I did not know was a fact — and do not yet,” he wrote in an 1852 letter to the prolific mathematician and physicist William Hamilton.

“我的一个学生今天要求我为一个事实提供一个理由，而我当时并不知道这个事实——而且现在还不知道，”他在 1852 年写给多产数学家和物理学家威廉·汉密尔顿的信中写道。

They met a skeptical audience.

他们遇到了持怀疑态度的观众。

Computers at the time were scary, technically unknowable.

当时的计算机很可怕，技术上不可知。

Appel and Haken were using core memory, storing information on magnetic material that was hand-woven into a mesh of wires.

阿佩尔和哈肯正在使用核心存储器，将信息存储在手工编织成金属丝网的磁性材料上。

“There were all kinds of arguments about how you can possibly trust this proof,” said Ellen Gethner , a mathematician at the University of Colorado, Denver.

“关于如何才能相信这个证明，存在着各种各样的争论，”丹佛科罗拉多大学的数学家埃伦·盖特纳 (Ellen Gethner) 说。

“What happens if there’s a surge of electricity and you miss that one configuration that would have invalidated the proof?”

“如果出现电流激增，而你错过了一种会使证明无效的配置，会发生什么？”

Still, most people grew to eventually accept that “four colors suffice,” as the University of Illinois later announced on their postal meter stamps.

尽管如此，大多数人最终还是接受了“四种颜色就足够了”这一说法，正如伊利诺伊大学后来在他们的邮政邮票上宣布的那样。

And in 1997, a team of mathematicians put the matter to bed by simplifying Appel and Haken’s approach, using a computer to identify and check just 633 configurations.

1997 年，一组数学家通过简化 Appel 和 Haken 的方法，使用计算机识别和检查 633 种配置，解决了这个问题。

This time, the mathematical community accepted the result immediately.

这一次，数学界立即接受了这个结果。

But the story was far from over.

但故事还远未结束。

The latest chapter started on a Danish beach in 2015.

最新的篇章始于 2015 年的丹麦海滩。

Ken-ichi Kawarabayashi , a graph theorist at Japan’s National Institute of Informatics, was at a conference with Thorup, his longtime collaborator.

日本国家信息研究所的图论学家川原健一 (Ken-ichi Kawarabayashi) 正在与他的长期合作者索普 (Thorup) 一起参加会议。

The pair had recently published a major paper together (which would later win them the prestigious Fulkerson Prize, also awarded decades earlier to Appel and Haken for their four-color work).

两人最近共同发表了一篇重要论文（这篇论文后来为他们赢得了享有盛誉的富尔克森奖，几十年前阿佩尔和哈肯也因他们的四色作品而获得该奖）。

They now stood on the white sand of Nyborg, wondering what to do next.

他们现在站在尼堡的白色沙滩上，想知道下一步该做什么。

“We can’t really work on a small project,” Kawarabayashi recalled thinking.

“我们不能真正致力于一个小项目，”川原林回忆道。

The four-color theorem had been a huge influence throughout their careers.

四色定理对他们的整个职业生涯产生了巨大的影响。

It had inspired them, in part, to become graph theorists in the first place.

它在一定程度上启发了他们成为图论学家。

Yet they remained dissatisfied with one aspect of the 1997 result: It had given mathematicians a recipe for coloring any graph with four colors, but that recipe was inefficient.

然而，他们对 1997 年结果的一个方面仍然不满意：它为数学家提供了一种用四种颜色为任何图形着色的方法，但该方法效率低下。

For a graph with n vertices, the coloring process would require n 2 steps.

对于具有 n 个顶点的图，着色过程将需要 n 2 个步骤。

The problem was that if you were handed some large graph and wanted to color it, you would have to search through it for one configuration, remove it, then search for another configuration, remove that , and so on — until you’d reduced your graph to something that was clearly four-colorable.

问题是，如果你收到一些大图并想要对其进行着色，你将必须在其中搜索一种配置，将其删除，然后搜索另一种配置，将其删除，依此类推 - 直到你将图表缩小为明显可四种颜色的东西。

Video: David Richeson discusses the history and significance of the four-color theorem.

视频：大卫·里奇森讨论四色定理的历史和意义。

Kawarabayashi and Thorup, soon joined by Thomassen and Bojan Mohar of Simon Fraser University, wanted to identify an unavoidable set of configurations that could be reduced in parallel, rather than one by one.

Kawarabayashi 和 Thorup 以及西蒙弗雷泽大学的 Thomassen 和 Bojan Mohar 很快加入进来，希望确定一组不可避免的配置，这些配置可以并行减少，而不是逐个减少。

To do so, they’d have to guarantee that they could reduce each configuration without interfering with the colorings of the other configurations getting reduced at the same time.

为此，他们必须保证可以减少每种配置，而不会干扰同时减少的其他配置的颜色。

That would give them a far faster way to recolor a graph with just four colors.

这将为他们提供一种更快的方法，只需四种颜色即可对图表进行重新着色。

How to find these non-interfering configurations?

如何找到这些互不干扰的配置？

By searching widely.

通过广泛搜索。

In the 1976 and 1997 proofs of the four-color theorem, mathematicians focused only on regions that featured clusters of vertices with few connections.

在 1976 年和 1997 年四色定理的证明中，数学家只关注具有很少连接的顶点簇的区域。

Kawarabayashi, Mohar, Thomassen, and Thorup instead directed their attention to so-called flat areas of the graph, where every vertex is connected to six others, forming a triangular arrangement of edges.

相反，川原林、莫哈尔、托马森和托鲁普将他们的注意力转向了图中所谓的平坦区域，其中每个顶点都与其他六个顶点相连，形成边的三角形排列。

These areas form a sort of graphical no-man’s land: It’s harder to identify good configurations there, since flat regions lack the structure that’s usually used to prove a configuration’s reducibility.

这些区域形成了一种图形无人区：在那里识别良好的配置比较困难，因为平坦区域缺乏通常用于证明配置可还原性的结构。

But, the researchers figured, flat areas are also much more common.

但是，研究人员认为，平坦区域也更为常见。

And to reduce and recolor many configurations at once without letting them interfere with each other, they’d need a lot of options to choose from.

为了同时减少和重新着色许多配置而不让它们相互干扰，他们需要有很多选项可供选择。

Atsuyuki Miyashita (left) and Yuta Inoue helped search for important structures in regions of graphs that usually get ignored.

Atsuyuki Miyashita（左）和 Yuta Inoue 帮助寻找通常被忽略的图表区域中的重要结构。

The search for configurations in these regions would take two more minds — Kawarabayashi’s graduate students, Yuta Inoue and Atsuyuki Miyashita — and months of computing time.

寻找这些区域的配置还需要另外两个人——川原林的研究生井上雄太和宫下敦行——以及数月的计算时间。

“We were pretty naïve,” Thorup said.

“我们非常天真，”索鲁普说。

“I don’t think we had any clue it would take so long.” But eventually they landed on a new unavoidable set.

“我认为我们根本不知道会花这么长时间。”但最终他们来到了一个不可避免的新场景。

It was massive, consisting of 8,202 configurations.

它非常庞大，由 8,202 种配置组成。

But as they’d hoped, it was possible to reduce many of those configurations at the same time in a given graph, turning what had once been many steps into just a few.

但正如他们所希望的那样，可以在给定的图中同时减少许多配置，将曾经的许多步骤变成只有几个步骤。

Once again, the four-color theorem had been proved.

四色定理再次被证明。

And the new proof gave a far more efficient coloring algorithm: For a graph with n vertices, it required n (log n ) steps, a significant improvement over n 2 .

新的证明给出了一种更有效的着色算法：对于具有 n 个顶点的图，它需要 n (log n ) 步骤，比 n 2 有了显着的改进。

As with Kempe’s failed attempt more than a century ago, the greatest value of the new proof lies less with its headline result than with the new insights it provides into the nature of graphs.

与一个多世纪前肯普的失败尝试一样，新证明的最大价值不在于其标题结果，而在于它为图表本质提供的新见解。

By drawing on a different concept of reducibility and using overlooked parts of the graph, the work has revealed previously unknown structure in these important mathematical objects — and has given mathematicians new tools for understanding them.

通过利用不同的可约性概念并使用图表中被忽视的部分，这项工作揭示了这些重要数学对象中以前未知的结构，并为数学家提供了理解它们的新工具。

“Once you build up machinery, you find out what kind of problems you can solve,” Gethner said.

“一旦你建造了机器，你就会发现你可以解决什么样的问题，”盖特纳说。

For instance, graph theorists are interested not just in planar graphs, but in graphs that lie on all sorts of surfaces, such as the doughnut-shaped torus.

例如，图论学家不仅对平面图感兴趣，而且对位于各种表面上的图感兴趣，例如甜甜圈形环面。

These graphs have some of the same properties that the new work uncovered in planar graphs — making it possible to prove coloring theorems about them as well.

这些图具有一些与新研究在平面图中发现的相同属性——使得证明它们的着色定理成为可能。

The researchers behind the latest four-color result are now using their techniques to address these questions.

最新四色结果背后的研究人员现在正在使用他们的技术来解决这些问题。

Though obstacles remain, Thomassen said, “I think we have the right path.”

托马森说，尽管障碍依然存在，“我认为我们的道路是正确的。”

Meanwhile, the four-color disease lives on.

与此同时，四色疾病依然存在。

While Thomassen is pleased with his recent result, he still has the same question that has dogged hobbyists and professionals alike for 150 years: Is there a simpler explanation for why four colors suffice for any planar graph?

虽然托马森对他最近的结果感到满意，但他仍然有一个困扰业余爱好者和专业人士 150 年来的问题：对于为什么四种颜色足以满足任何平面图，是否有更简单的解释？

The mythical one-pager, the theoretical flourish that would make everyone go “aha”?

神话般的一页纸，理论的繁荣会让每个人都惊叹不已？

“What I would like is a proof without the use of a computer,” Thomassen said.

“我想要的是不使用计算机的证明，”托马森说。

“And I will never stop thinking about that.”

“我永远不会停止思考这个问题。”

Get highlights of the most important news delivered to your email inbox

获取发送到您的电子邮件收件箱的最重要新闻的摘要

Quanta Magazine moderates comments to facilitate an informed, substantive, civil conversation.

《Quanta》杂志对评论进行审核，以促进知情、实质性、文明的对话。

Abusive, profane, self-promotional, misleading, incoherent or off-topic comments will be rejected.

辱骂、亵渎、自我推销、误导、语无伦次或偏离主题的评论将被拒绝。

Moderators are staffed during regular business hours (New York time) and can only accept comments written in English.

版主在正常工作时间（纽约时间）有工作人员，并且只能接受英文评论。