Four Color Theorem: What the 2026 Proof Changes

Quick answer: The four color theorem says that every finite map on a plane or sphere, with each region in one connected piece, can be colored with at most four colors so that regions sharing a border segment get different colors. Regions meeting only at a point may share a color. Kenneth Appel and Wolfgang Haken first proved it in 1976 with computer help, and a 2026 proof by six mathematicians made finding such a coloring dramatically faster.

2026 update (checked November 21, 2026): In March 2026, Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen and Mikkel Thorup posted a new computer-assisted proof that comes with an \(O(n\log n)\) coloring algorithm. A follow-up paper posted in October 2026, “Four-Coloring Planar Graphs in Linear Time,” improves the theoretical running time to \(O(n)\), where \(n\) is the number of regions (graph vertices). Four colors have been known to suffice since 1976; the new work changes how efficiently a coloring can be found.

Grab a map of the United States and some colored pencils. Color each state so that neighbors never match. How many colors do you need? Try it and you will find that four always seem to be enough, while three are not. In 1852 a young student named Francis Guthrie noticed this while coloring a map of English counties. Proving it took more than a century, a famous wrong proof, and the first major proof in history that depended on a computer.

What Does the Four Color Theorem Say?

Any map drawn on a flat surface can be colored with at most four colors so that regions sharing a border have different colors. Regions that meet only at a single point, like the Four Corners of Arizona, Colorado, New Mexico and Utah, may share a color. Each region must also be one connected piece.

Mathematicians usually restate it with graphs: put a dot in each region and join two dots when the regions share a border. The result is a planar graph, one that can be drawn without crossing edges, and the theorem says every planar graph’s vertices can be colored with four colors so that joined dots differ.

Why Are Three Colors Not Enough?

Picture a central region completely surrounded by a ring of three others, each touching the center and its two neighbors in the ring. All four regions touch each other, so they need four different colors.

A real example is Nevada. Its five neighbors (Oregon, Idaho, Utah, Arizona and California) form a ring, and each touches the next. A ring with an odd number of regions cannot alternate between two colors: try coloring A, B, A, B, and the fifth region touches both an A and a B, so the ring needs three colors. Nevada touches all five, so it cannot reuse any of those three and needs a fourth. Notice that having five neighbors alone proves nothing; it is the odd ring that forces the extra color.

From Map to Graph: The Rule That Matters

On the mapIn the graphMust the colors differ?
A regionA dot (vertex)Not applicable
Two regions share a border segmentThe dots are joined by an edgeYes
Two regions touch only at a corner pointNo edgeNo

A Short History of the Proofs

YearEvent
1852Francis Guthrie asks whether four colors always suffice.
1879Alfred Kempe publishes a proof that is accepted for 11 years.
1890Percy Heawood finds the flaw in Kempe’s proof and proves that five colors always suffice.
1976Kenneth Appel and Wolfgang Haken prove the theorem using a computer to check about 1,900 configurations.
1997Robertson, Sanders, Seymour and Thomas give a simpler computer proof with 633 configurations.
2005Georges Gonthier fully formalizes the proof in the Coq proof assistant.
March 2026A new proof by Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen and Thorup, with a near-linear coloring algorithm.
October 2026A follow-up paper gives a linear-time four-coloring algorithm.

All modern proofs follow the same strategy. First find an unavoidable set: a list of small map patterns, at least one of which must appear in every map. Then show each pattern is reducible: if a smaller map can be four-colored, the coloring can be extended to the pattern. The list is long, so computers check the cases.

What Is New About the 2026 Proof?

Quanta Magazine reported in September 2026 that Carsten Thomassen, Mikkel Thorup, Ken-ichi Kawarabayashi, Bojan Mohar and Kawarabayashi’s students Yuta Inoue and Atsuyuki Miyashita found a new proof, posted online in March 2026. A few key facts:

  • Still a computer proof. It uses an unavoidable set of 8,202 configurations, compared with 633 in 1997, and in some ways it is even more complicated than before.
  • A faster algorithm. The reducible configurations are found in “flat” areas of the map and can be handled in parallel. This gives a way to four-color a map with \(n\) regions in about \(n \log n\) steps, instead of the roughly \(n^2\) steps of the 1997 method. The 8,202 configurations describe the proof machinery, not the number of steps needed to color any one map.
  • New structure. The proof gives new insight into how planar graphs are built, which matters for computer science and network design.
MethodTime to four-color a map with \(n\) regions
Robertson, Sanders, Seymour and Thomas (1996 to 1997)\(O(n^2)\)
Inoue et al., March 2026\(O(n\log n)\)
Follow-up paper, October 2026\(O(n)\)

These are theoretical running times. They tell you how the work grows as maps get bigger, not how many seconds a particular program takes.

Thomassen told Quanta that what he would really like is “a proof without the use of a computer.” Nobody has found one yet.

Where Is the Four Color Theorem Used?

Coloring problems show up whenever conflicting items must be kept apart: assigning radio frequencies so nearby towers do not interfere, scheduling exams so no student has two at once, or assigning registers in a computer program. These conflict graphs are usually not planar, so the four color guarantee does not apply to them; planar maps are a special, well-understood case, and ideas from the planar proofs feed into the wider theory.

Common Misconceptions

“Four colors work on any surface.” No. Some maps on a torus (a donut shape) require seven colors.

“The theorem was proved by hand.” No proof so far avoids computer checking, although the proof has been formally verified.

“Regions meeting at a point must differ.” No. Only regions that share a border segment must have different colors.

Watch: The Four Color Theorem in Video

If you learn better by watching, these videos are worth your time.

The Four Color Map Theorem (Numberphile). A friendly 14-minute introduction to the theorem and its history.
The Four Color Theorem: What Counts as a Proof? (Up and Atom). Why the computer proof caused controversy.
John Conway: Four Color Theorem and Computer Proofs (Simons Foundation). The late John Conway on computer-assisted proofs.

Check Your Understanding

Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.

Answer each question and press Submit to see your result right away.

1. What is the most colors any flat map needs so neighbors never match?
Found a bug? Let us know!
2. Who found the flaw in Kempe’s 1879 proof?
Found a bug? Let us know!
3. Do two regions that meet at a single point need different colors?
Found a bug? Let us know!
4. About how many configurations does the 2026 proof use?
Found a bug? Let us know!
5. How many colors can some maps on a torus need?
Found a bug? Let us know!

Frequently Asked Questions

What is the four color theorem?

It states that the regions of any map on a flat surface can be colored with at most four colors so that no two regions sharing a border have the same color.

Who proved the four color theorem?

Kenneth Appel and Wolfgang Haken proved it in 1976 with computer help. Robertson, Sanders, Seymour and Thomas simplified the proof in 1997, Georges Gonthier formalized it in 2005, and a new proof by Thomassen, Thorup and four colleagues appeared in 2026.

Is the new 2026 proof computer-free?

No. Like every known proof, the 2026 proof relies on computer checks of many configurations. Its main advance is a faster method for finding a four-coloring, and a follow-up paper brought that down to linear time. A proof without a computer remains an open challenge.

Why is the four color theorem important?

It was the first major theorem proved with essential computer help, which changed debates about what counts as a proof, and map-coloring ideas are used in scheduling, frequency assignment and computer science.

Keep Exploring

Sources and Further Reading

Related to This Article

What people say about "Four Color Theorem: What the 2026 Proof Changes - Effortless Math"?

No one replied yet.

Leave a Reply