Five color theorem

Every planar graph has a vertex coloring with at most five colors in which adjacent vertices receive different colors. It is a constructive result proved by reducing a coloring problem to smaller planar graphs.

Planar graph: A graph that can be drawn in the plane with no edges crossing except at shared endpoints. The theorem applies precisely to this class of graphs.
Francis Guthrie: A British mathematician who posed the map-coloring problem that led to the four-color conjecture. His question about coloring English counties began the chain of results behind the theorem.
Six color theorem: Every planar graph can be vertex-colored with at most six colors so adjacent vertices differ. It gives a simpler, weaker bound than the five-color theorem.
Map coloring problem: The problem of coloring map regions so that regions sharing a boundary have different colors. Representing regions as graph vertices makes the theorem a direct coloring guarantee.
Graph coloring: An assignment of colors to graph elements subject to constraints such as different colors on adjacent vertices. The theorem is a universal upper bound for vertex coloring on planar graphs.
Augustus De Morgan: A British mathematician whose correspondence helped circulate the map-coloring problem in the nineteenth century. He received Guthrie's question and brought it to other mathematicians' attention.
Four color theorem: Every planar graph can be vertex-colored with at most four colors so adjacent vertices differ. It sharpens the five-color upper bound by one color.
Greedy graph coloring: A graph-coloring algorithm that assigns each vertex an available color in a chosen order. A suitable removal order colors every planar graph with at most six colors; recoloring improves the bound to five.
Euler's formula: For a connected planar graph, the numbers of vertices, edges, and faces satisfy V − E + F = 2. It bounds planar edge density, ensuring a vertex of degree at most five.
Arthur Cayley: A British mathematician who contributed to algebra, geometry, and the early study of map coloring. His 1879 publication helped prompt Alfred Kempe's influential, flawed proof attempt.

Linked from 1 page