Skip to main content
London Tutorsby KnowledgeDottCom

5 November 2026 · London Tutors

The Four-Colour Theorem Gets a Rare New Proof — and a Much Faster Way to Colour Maps

Four colours are enough for any map — but proving it has taken nearly 150 years and several computer-assisted proofs. A new proof from an international team also colours maps far faster than before.

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.

Ready to find the right tutor?

Browse verified tutors, compare profiles, and book a trial lesson — free to sign up.

Find a tutor — sign up free

Related guides