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 map | In the graph | Must the colors differ? |
|---|---|---|
| A region | A dot (vertex) | Not applicable |
| Two regions share a border segment | The dots are joined by an edge | Yes |
| Two regions touch only at a corner point | No edge | No |
A Short History of the Proofs
| Year | Event |
|---|---|
| 1852 | Francis Guthrie asks whether four colors always suffice. |
| 1879 | Alfred Kempe publishes a proof that is accepted for 11 years. |
| 1890 | Percy Heawood finds the flaw in Kempe’s proof and proves that five colors always suffice. |
| 1976 | Kenneth Appel and Wolfgang Haken prove the theorem using a computer to check about 1,900 configurations. |
| 1997 | Robertson, Sanders, Seymour and Thomas give a simpler computer proof with 633 configurations. |
| 2005 | Georges Gonthier fully formalizes the proof in the Coq proof assistant. |
| March 2026 | A new proof by Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen and Thorup, with a near-linear coloring algorithm. |
| October 2026 | A 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.
| Method | Time 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.
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.
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
- Quanta Magazine: The Four-Color Theorem Gets a Rare New Proof (Sept 10, 2026)
- Inoue, Kawarabayashi, Miyashita, Mohar, Thomassen and Thorup, The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring (arXiv 2603.24880)
- Four-Coloring Planar Graphs in Linear Time (arXiv 2610.39753)
- University of Illinois Distributed Museum: The Four Color Theorem
- Wolfram MathWorld: Four-Color Theorem
Related to This Article
More math articles
- A 4-Week Grade 7 ELA Study Plan: Reading, Writing, Vocabulary, and Review That Actually Fits Real Life
- Main Ideas vs. Supporting Details in Science
- Calculus Derivatives and Integrals Flashcards
- Executive privilege
- The Best Grade 6 ELA Practice Tests for Washington Students
- The Best Grade 6 ELA Practice Tests for New Mexico Students
- The Best Grade 3 Math Book for Maryland Students
- Exploring the Fundamentals: Properties of Equality and Congruence in Geometry
- Life Course, New Roles, and Resocialization
- Lenses and Optical Instruments


What people say about "Four Color Theorem: What the 2026 Proof Changes - Effortless Math"?
No one replied yet.