Science1 publisher3 min readPublished
New four-color theorem proof buys planar-graph insight with more computation
Six researchers spent nearly a decade building a third computer proof of the four-color theorem, one that runs longer than the proofs that came before it. Their return was a much faster coloring method plus new structure in planar graphs.
The Scientist · Science desk
What happened
- Mikkel Thorup, Carsten Thomassen and four colleagues in Denmark, Canada and Japan spent nearly a decade building another computer proof of the four-color theorem.
- The proof went online in March 2026 and is scheduled for presentation in November at the annual Foundations of Computer Science conference.
- Building the argument produced a far more efficient way to color maps, which is the part of the work with a use beyond the theorem itself.
Compiled by The ScientistSomething wrong?How this is made
Why it matters
- constraint A decade spent hunting a simpler reason the theorem is true ended in a longer machine-backed argument, so this result cannot be cited as evidence that brute-force enumeration is being converted into proofs a person can check by hand.
- capability Since nobody doubted the theorem, the part of this work that changes what anyone can do is the coloring procedure, which is an artifact you run rather than a conclusion you accept.
- precedent If the planar-graph structure travels to other problems, future four-color papers get judged on what they unlock elsewhere rather than on how few pages they take.
The word carrying the most weight in Quanta Magazine's account is "efficient," and it is not describing the proof. The new argument is, by that account, in some ways more complicated than the computer proofs before it [8], while the map-coloring method that fell out of building it is far more efficient [10]. Those are two different objects: one a document referees have to check, the other a procedure you run on a graph. A long document can contain a fast procedure, and here it apparently does.
What the account gives is a direction rather than a number: it doesn't specify a runtime, a complexity bound, or a comparison against the coloring method implied by earlier proofs [21]. "Far more efficient" is a direction rather than a measurement, and the November presentation at the Foundations of Computer Science conference [7] is where that either gets pinned down or does not.
There is also nothing here pointing toward hand-verification. Georges Gonthier of Inria in Paris, reading the work, said it looks like the authors "used electricity liberally in actually carrying out their proof" [9]. Count the original computer proof, whose methods were treated as scandalous [4], and the simpler computer-assisted one that settled the argument in 1997 [5], and this is at least the third machine-backed proof of the same statement [19]. The computation went up, even though the motivation behind the project pointed the other way: Mikkel Thorup and Carsten Thomassen went in on the belief that a statement this simple must have a simpler reason behind it, or failing that a more efficient way to demonstrate it [22]. They got the second thing.
The attrition rate on the first ambition is worth knowing. Alfred Bray Kempe's claimed solution was announced in Nature in 1879 and stood 11 years before it was shown to be wrong [3][2], which puts its collapse in 1890 [17]. Wrong answers kept coming, from lawyers, doctors and well-known graph theorists [16]. Francis Guthrie's 1852 observation while coloring English counties [14] took 145 years to stop being contested [20]. Thomassen's account of why so many people crashed into it: "Here we have a problem that even a child can understand" [12].
The operationally interesting output is the structural work. Kempe's move of discarding the geography and keeping only the adjacency graph is what turned map coloring into graph coloring in the first place [15], and Quanta reports that the new proof uncovered structural properties of planar graphs that open up the potential for progress on other stubborn problems in graph theory [11]. "Potential" is the honest word there; the results have not yet been transferred to another problem.
So what six researchers have to show for nearly a decade [18][6] is an algorithm and a batch of structural facts about planar graphs. That is a real return, and the currency is graph algorithms, not pages saved.
What to watch
- Whether the November presentation or the final paper attaches an actual bound to the coloring method that Quanta describes only as far more efficient.
- Whether the planar-graph structural results get used to move another graph theory problem, by someone outside the six-author group.
- Whether the computational parts of the argument can be checked independently of the authors' own code.