Overview

The four color theorem states that any separation of a plane into contiguous regions (commonly thought of as the countries on a political map) can be colored using no more than four colors so that no two regions that share a boundary segment have the same color. In graph-theoretic language this is equivalent to saying every planar graph can have its vertices colored with at most four colors so adjacent vertices receive different colors. This equivalence uses the dual graph construction: regions correspond to vertices and shared borders to edges.

Key characteristics and formulation

The typical formulation requires that regions sharing only a single point (a corner) are not considered adjacent; adjacency requires a nontrivial common boundary segment. The theorem applies to subdivisions of the sphere as well as the plane, since they are topologically the same. For surfaces of higher genus (for example, a torus) the number of colors needed can be larger; these cases are treated by the Heawood formula and related results for different surfaces.

History and major milestones

The problem originated in the mid-19th century, when it was posed in 1852. Early attempts included a widely circulated but flawed proof by Alfred Kempe in 1879; his argument stood for a decade before a gap was discovered. A simpler and reliable result, the five color theorem, was proved in the 1890s and shows five colors always suffice. The four color statement proved far more resistant and spurred much research in graph theory and combinatorics.

  • 1852: first public statement of the problem.
  • 1879: Kempe's influential but incorrect proof and later correction.
  • 1890s: the five color theorem established a basic upper bound.
  • 1976: the first widely accepted proof using extensive computer verification.
  • 1990s: computer-assisted proofs refined and simplified the case analysis.

Proof methods and the role of computers

Proof strategies center on reducing the infinite variety of maps to a finite, unavoidable set of configurations and then showing each configuration is reducible. Historically this led to very large case analyses. The first complete proof accepted by most mathematicians used a computer to check many cases by exhaustion and introduced controversy because routine but extensive checking was delegated to software. Later work reduced the number of configurations and streamlined parts of the argument, but all known correct proofs rely substantially on computer verification for case checking.

Uses, examples, and significance

Although the original motivation came from coloring political maps, practical mapmaking rarely requires four colors in a deliberate way — many real-world maps need only three or fewer. The theorem's importance is primarily theoretical: it helped to establish methods in graph theory, stimulated the development of discharging techniques and the theory of planar graphs, and raised philosophical questions about computer-assisted proofs and mathematical rigor. Simple examples that force four colors include arrangements where a region is surrounded by an odd cycle of mutually adjacent regions.

Closely related topics include the five color theorem, the Heawood problem for other surfaces, and coloring variants for planar graphs (edge coloring, list coloring). For introductions and technical accounts, consult standard graph theory texts and survey articles. Additional resources and historical commentary are available via the following references and further reading links:

  1. General overview of the theorem
  2. Graph-theoretic formulation
  3. Topological background and planar maps
  4. Definitions of adjacency and regions
  5. Historical notes on the map problem
  6. Technical discussion of borders and adjacency
  7. Computer-assisted proof approaches
  8. Exposition of proof by exhaustion
  9. Examples and constructions requiring four colors
  10. The five color theorem and comparisons

Note: This article summarizes widely accepted elements of the subject and points to standard developments; readers seeking formal proofs and complete technical details should consult specialized literature and the referenced sources above.