Veripedia

Four-color theorem

The four-color theorem states that any map drawn on a plane or sphere can have its regions colored with no more than four colors so that regions sharing a boundary line have different colors. Equivalently, every loopless planar graph has a proper vertex coloring with at most four colors. First posed in the nineteenth century, the theorem became famous for its computer-assisted proof.

Last updated
20 October 2026
Confidence
High (98%)
Sources
5
Versions
1
This article was researched and drafted with AI assistance and checked by an automated review pass. It is not guaranteed to be accurate — verify important facts against the references below.

Statement and meaning

In the map formulation, each region must receive a color different from that of any region sharing a boundary line with it. Regions that meet only at a single point do not count as adjacent for this purpose. The result says that four colors always suffice; it does not require every map to use all four. In graph theory, the equivalent statement is that every loopless planar graph can have its vertices colored with at most four colors so that the endpoints of every edge have different colors. A graph is planar if it can be drawn in the plane without edges crossing.

A long-standing conjecture

The problem was posed by Francis Guthrie in 1852. Alfred Kempe announced a proof in 1879, and it was accepted for a time. In 1890, Percy Heawood identified a flaw in Kempe's argument. Although this returned the four-color problem to conjecture status, Heawood adapted part of the approach to prove that five colors suffice for every planar map. The distinction is important: establishing a five-color bound did not settle whether four colors were always enough.

The computer-assisted proof

Kenneth Appel and Wolfgang Haken announced a proof in 1976. Their argument reduced the general problem to a finite collection of configurations and used a computer to check the cases required by the reduction. The mathematical reasoning and the computation worked together: the computer checked a large, explicitly generated set of cases, rather than replacing the theorem's logical argument. Because not all of those checks could conveniently be repeated by hand, the proof prompted debate about how computer-assisted results should be verified. Later scrutiny and corrected details established the result as a theorem.

Later proofs and formal verification

In 1997, Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas published a simpler proof that also used computer calculations. Georges Gonthier later formalized the proof in the Coq proof assistant; he reported completing the formalization in 2005. A proof assistant checks a proof expressed in a precise formal language, providing a different kind of verification from rerunning a program that checks cases. These developments made the theorem an influential example in discussions about proof, computation and the reliability of mathematical software.

Key facts

Theorem
Every planar map can be colored with at most four colors so that regions sharing a boundary line have different colors.
Graph formulation
Every loopless planar graph has a proper vertex coloring using at most four colors.
Origin
Francis Guthrie posed the problem in 1852.
First proof
Kenneth Appel and Wolfgang Haken announced a computer-assisted proof in 1976.
Formal verification
Georges Gonthier completed a formalization of the proof using Coq in 2005.

Timeline

  1. 1852

    Francis Guthrie posed the map-coloring problem that became the four-color conjecture.

  2. 1879

    Alfred Kempe announced a proof, later found to contain a flaw.

  3. 1890

    Percy Heawood identified the flaw in Kempe's proof and proved the five-color theorem.

  4. 1976

    Appel and Haken announced the first proof of the four-color theorem, using computer-assisted case checking.

  5. 1997

    Robertson, Sanders, Seymour and Thomas published a simpler proof that also used a computer.

  6. 2005

    Gonthier completed a formalization of the proof in the Coq proof assistant.

Ask about this article

Answers use only “Four-color theorem” and its references, with citations.

References

  1. 1.
    The Four-Color Theorem 1852–1976

    American Mathematical Society, Notices of the AMS · other · reliability: high · retrieved 20 October 2026

    Supports: The problem's origin, the mistaken Kempe proof, the 1976 solution, computer-assisted reasoning and later developments.

  2. 2.
    Four-Color Theorem

    Wolfram MathWorld, Wolfram Research · other · reliability: high · retrieved 20 October 2026

    Supports: The map-coloring statement, the meaning of adjacency and historical overview.

  3. 3.
    The four colour theorem

    MacTutor History of Mathematics, University of St Andrews · other · reliability: high · retrieved 20 October 2026

    Supports: Historical account of the conjecture, Kempe's proof, Heawood's correction and the five-color result.

  4. 4.
    The Four-Colour Theorem

    Journal of Combinatorial Theory, Series B, Elsevier · other · reliability: high · retrieved 20 October 2026

    Supports: The 1997 scholarly proof and its abstract's description of the theorem and computer-assisted proofs.

  5. 5.
    Formal Proof—The Four-Color Theorem

    American Mathematical Society, Notices of the AMS · other · reliability: high · retrieved 20 October 2026

    Supports: Gonthier's formalization of the theorem's proof and use of the Coq proof assistant.

References are suggested by the research engine and may be incomplete. Unverified URLs are omitted rather than guessed.

Article history

  1. Version 120 October 2026 · EditorCreated by Zapia