The Four-Colour Theorem Gets a Rare New Proof — and a Much Faster Way to Colour Maps
Here is a puzzle you can try at home: take any map, with countries of any shape, and colour it so that no two neighbours share a colour. How many colours do you need? The answer, mathematicians believe, is four — always. That claim is the four-colour theorem, and it has haunted mathematicians for nearly 150 years. Now it has a rare new proof, and the new proof comes with a bonus: a much faster way to do the colouring.
The result is reported by Quanta Magazine and comes from a team of six mathematicians in Denmark, Canada and Japan: Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen and Mikkel Thorup. Their paper, "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring", was posted online in March 2026 and will be presented at the Foundations of Computer Science conference in New York on 8–11 November 2026.
A problem with a long, stubborn history
The question was first asked in the 1850s. The first claimed proof, announced in 1879, stood for eleven years before it was shown to be wrong. The theorem was finally proved in the 1970s, when Kenneth Appel and Wolfgang Haken used a computer to check hundreds of cases — a proof many mathematicians found unsatisfying, because no human could check it by hand. A second computer proof followed in the 1990s.
The new proof is also computer-assisted, and in some ways even more complicated than its predecessors: it rests on a set of 8,202 configurations that a computer must check. But it proves something stronger than the old proofs. Where earlier proofs found one reducible pattern at a time, the new proof shows that a map always contains many such patterns at once — so many that each round of colouring can shrink the problem by a large fraction instead of a little.
Faster colouring, not just a new proof
That stronger result gives a far more efficient colouring method. For a map-like network with n points, the new algorithm needs about n log n steps, a big improvement on the n² steps of the best method from 1996, by Robertson, Sanders, Seymour and Thomas. It is the first real speedup in three decades, and it is close to the best possible: simply reading the input already takes about n steps.
Some mathematicians still dream of a short proof a person could read and check by hand. That dream is still unfulfilled. But the new proof shows that an old problem can still surprise us — and that a fresh idea about how to organise a proof can turn a decades-old method into something much faster.
If your child enjoys puzzles like this, a first lesson in maths can start with colouring a map and end with the same ideas mathematicians use to study networks, timetables and computer chips. Book your first lesson
Sources:
- Inoue, Y. et al., "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring", arXiv:2603.24880 (2026): https://arxiv.org/abs/2603.24880
- Barber, G., "The Four-Color Theorem Gets a Rare New Proof", Quanta Magazine, 4 November 2026: https://www.quantamagazine.org/the-four-color-theorem-gets-a-rare-new-proof-20260910/
London Tutors — post your tutoring request and we will match you with a verified tutor.