The Four Color Theorem and Its Meaning

What the Four Color Theorem Says

A map-coloring problem asks how many colors are needed so that neighboring regions receive different colors. The answer is strikingly uniform: four colors suffice, however complicated the planar arrangement. The theorem is an upper bound, not a claim that every map needs four colors. A tetrahedral map does need all four, so the bound cannot be lowered.

All graphs in the graph-theoretic statement are finite and simple. A graph is planar if it can be drawn in the plane with edges meeting only at common endpoints. A plane graph is a planar graph together with a particular such drawing, called an embedding. A planar graph describes whether a crossing-free drawing exists; a plane graph also records which drawing is being used.

The map statement uses edge-sharing as the rule for adjacency: two regions that meet only at a point are not required to have different colors. A region is a connected component of the complement of the embedded graph. The theorem is a deep result; its substantial proof is not supplied here. This tutorial establishes the precise connection between its graph and map formulations, and explains what the bound does and does not say.

Why Vertex Coloring and Region Coloring Match

For a plane graph, its plane dual has one vertex for each region, and an edge across each edge of the original graph, joining the vertices for the regions on the two sides. If an edge has the same region on both sides, the corresponding dual edge is a loop. If two regions share more than one edge, the dual has parallel edges. Thus the dual need not be simple. For coloring regions, loops impose no condition between distinct regions, and parallel edges repeat the same condition. Deleting loops and replacing parallel edges by a single edge leaves exactly the constraints relevant to a proper coloring.

Proof. First assume the graph statement. Given a finite plane map, form its dual and discard loops and duplicate parallel edges. The resulting graph is simple and planar: it is drawn by the dual construction, with the discarded edges removed. Its vertices correspond to the regions of the map, and its edges correspond exactly to pairs of distinct regions sharing an edge. The graph statement colors these vertices with at most four colors. Transferring each vertex's color to its corresponding region gives the required map coloring.

Now assume the map statement. Start with a connected plane graph \(G\), and form its plane dual \(G^*\). The standard plane-duality facts are that the regions of \(G^*\) correspond to the vertices of \(G\), and two such regions share an edge exactly when the corresponding vertices of \(G\) are joined by an edge. Applying the map statement to \(G^*\) therefore gives a proper coloring of \(G\)'s vertices with at most four colors. For a disconnected planar graph, apply this argument to each connected component in a plane embedding and use the same palette of four colors for every component. No edge joins different components, so the combined coloring is proper. The empty graph has no vertices and needs no colors. Thus the graph statement follows. \(\square\)

The proposition is an equivalence of statements, not an assertion that a particular graph and its own regions receive identical color assignments. Duality changes vertices into regions and edges into region adjacencies. The coloring is transferred between these corresponding objects.

Disconnected Graphs and Maps

Proof. Restrict any proper coloring of \(G\) to a component \(G_i\). The restriction remains proper, so a coloring of \(G\) uses at least \(\chi(G_i)\) colors for every \(i\). Hence \(\chi(G)\ge\max_i\chi(G_i)\). Conversely, let \(q=\max_i\chi(G_i)\). Color each component properly using colors from the same set \(\{1,\ldots,q\}\). Every edge belongs to one component, so its endpoints receive different colors. The combined coloring is proper and uses at most \(q\) colors. Therefore \(\chi(G)\le q\), proving equality. \(\square\)

This explains why a disconnected graph does not need separate, non-overlapping palettes for its components. The same colors can be reused because there are no edges between components. In a disconnected plane map, the regions still have to be checked according to their actual shared boundaries; the components of the embedded graph are not themselves the map's regions.

What the Bound Means—and a Common Pitfall

The theorem guarantees a coloring with at most four colors. It does not say that four colors are always necessary, and it does not say that any arbitrary assignment of four colors is valid: every edge or region adjacency must still be checked. The \(K_4\) example shows sharpness, while a graph with no edges needs at most one color if it has vertices.

A map may also have an edge whose two sides belong to the same region. In the dual this edge becomes a loop. A frequent mistake is to interpret that loop as an instruction that the region must have a different color from itself. For example, embed the path with \(V=\{1,2,3\}\) and \(E=\{12,23\}\) in the plane. Its complement has one region, so the map needs just one color. The dual has one vertex and two loops, one for each path edge. If one applies the usual simple-graph rule to those loops, one would incorrectly declare the coloring impossible. The correction is to apply the map rule: only two distinct regions sharing an edge must differ. A loop records the same region on both sides and creates no such pair. After loops are ignored, the region-adjacency graph has one vertex and no edges, correctly requiring one color.

These distinctions keep the theorem's scope precise: planar concerns the existence of an embedding, plane records a chosen embedding, and map coloring concerns distinct regions that share an edge. Duality translates the last condition into vertex coloring without turning a region's boundary with itself into an extra color constraint.