40.04.08 · combinatorics / graph-theory-core

Map Colouring: the Five-Colour Theorem and the Four-Colour Theorem

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1 and the discharging discussion; Mohar-Thomassen 2001 *Graphs on Surfaces* (Johns Hopkins) Ch. 8 (colouring graphs on surfaces, the Heawood number, the Ringel-Youngs theorem); Robertson-Sanders-Seymour-Thomas 1997 (the modern four-colour proof and discharging); the original sources Heawood 1890, Kempe 1879, Appel-Haken 1977, Tait 1880, Ringel-Youngs 1968

Intuition Beginner

Look at a map of countries and ask: how many colours do you need so that no two countries sharing a border get the same colour? Touching at a single point does not count as sharing a border, only a stretch of common boundary. People have coloured maps this way for centuries, and the surprising answer is that four colours always suffice, no matter how tangled the map. Three are sometimes not enough, and a famous theorem says you never need a fifth.

To study this with graphs, shrink each country to a single dot and draw a line between two dots whenever those countries share a border. This new picture is a graph, and because the countries lay flat on the page with borders that do not cross, the graph can also be drawn without crossings. Colouring the map so neighbours differ becomes colouring the dots so that joined dots differ — the same proper-colouring question from the colouring unit, now asked only about flat, crossing-free graphs.

Reducing the colour count is hard. Showing that six colours always work is short; showing that five always work takes a clever swapping trick; showing that four always work resisted everyone for over a century and was finally settled in 1976 with help from a computer checking thousands of cases. This unit walks up that ladder, from the easy six down to the deep four.

Visual Beginner

Picture a small map: one central country surrounded by a ring of five countries, each ring country bordering the centre and its two ring neighbours. Place a dot in each country and join dots whose countries share a border. The centre dot joins all five ring dots, and the ring dots form a five-step loop, so the dual graph is a centre joined to a five-cycle.

The table records a colouring. The centre takes one colour. The five-country ring is an odd loop, so it cannot be coloured with just two colours; it needs three. Together with the centre's colour, the whole map needs four.

region	borders	colour
centre	all five ring regions	1
ring A	centre, ring B, ring E	2
ring B	centre, ring A, ring C	3
ring C	centre, ring B, ring D	2
ring D	centre, ring C, ring E	3
ring E	centre, ring D, ring A	4

This little map needs four colours and no fewer, which shows four is sometimes necessary. The four-colour theorem says four is also always enough.

Worked example Beginner

Show by hand that a flat, crossing-free graph with few enough lines can always be coloured with six colours, using one country at a time. Take any such graph and find a dot with at most five lines touching it; the planarity unit guarantees one always exists. Call it $d$ .

Step 1. Set $d$ aside for a moment and colour everything else first, assuming we already know the smaller picture can be done with six colours.

Step 2. Bring $d$ back. It touches at most five other dots, so at most five colours are used up by its neighbours.

Step 3. Pick a free colour for $d$ . With six colours available and at most five blocked, at least one colour remains. Give $d$ that colour.

Step 4. Check the rule still holds. Every line from $d$ goes to a neighbour with a different colour, and the rest of the picture was already coloured correctly, so the whole graph now uses six colours properly.

Step 5. See why the size shrinks. Each time we remove a low-line dot, the graph gets smaller, so repeating the idea eventually reaches a single dot, which needs one colour. Building back up, six colours carry through every step.

What this tells us: the one fact that every flat graph hides a dot with at most five lines turns into a colouring recipe. The same removal idea, pushed much harder, is what gives five colours and, with enormous extra effort, four.

Check your understanding Beginner

Formal definition Intermediate+

A map is a subdivision of the sphere $S^{2}$ (equivalently the plane, with one unbounded region) into finitely many connected regions, the countries, by a plane graph whose edges are the borders; two countries are adjacent when their closures share an arc of border, not merely a point ^{[West 2001 §6.3]}. The map-colouring problem asks for the least number of colours assigning each country a colour so that adjacent countries differ. Passing to the dual of the underlying plane graph (one vertex per country, one edge per shared border arc, as fixed in 40.04.05) turns this into vertex colouring: a proper colouring of the map is exactly a proper vertex colouring of the dual plane graph in the sense of 40.04.06. The dual of a map is a plane graph, and conversely every plane graph is the dual of a map, so map colouring and the vertex colouring of planar graphs are the same problem. One restricts to bridgeless maps (no border with the same country on both sides), under which the dual is loopless.

The relevant invariant is therefore the chromatic number $χ (G)$ of a planar graph $G$ . Three thresholds organise the theory. The six-colour theorem asserts $χ (G) \leq 6$ , the five-colour theorem asserts $χ (G) \leq 5$ , and the four-colour theorem asserts $χ (G) \leq 4$ , for every loopless planar $G$ . The first follows at once from the light vertex; the second from a colour-swapping argument; the third is the deep result.

A Kempe chain is the engine of the classical arguments. Given a partial proper colouring and two colours $i, j$ , the $(i, j)$ -Kempe chain through a vertex $v$ coloured $i$ is the connected component of $v$ in the subgraph $G_{ij}$ induced by all vertices coloured $i$ or $j$ . Swapping the two colours throughout one such component yields another proper colouring, because the only edges leaving the component go to vertices coloured neither $i$ nor $j$ , which the swap does not touch ^{[Diestel 2017 §5.1]}. This Kempe swap is the move that frees a colour at a chosen vertex.

Counterexamples to common slips

Four colours is an upper bound, not the exact number. Many maps need only one, two, or three colours; $χ (G) \leq 4$ caps the worst case. A planar triangle forces three, and the dual of the centre-plus-five-ring map forces four, but no planar map forces five.
The bound is special to the plane. On the torus the analogous bound is seven, and $K_{7}$ embeds there, so do not carry $χ \leq 4$ to other surfaces. The plane and sphere are the surfaces of Euler characteristic two.
A single Kempe swap need not fix a five-colour configuration into a four-colour one. Kempe's own four-colour proof failed exactly because two simultaneous swaps can interfere. The five-colour theorem survives because one swap at a degree-five vertex with two non-adjacent like-coloured neighbours always succeeds.
Adjacency requires a shared arc. Countries meeting at a single point are not adjacent; otherwise a point where many regions meet would behave like a clique and break the planar bound.

Key theorem with proof Intermediate+

Theorem (six- and five-colour theorems). Every loopless planar graph $G$ satisfies $χ (G) \leq 5$ ; in particular $χ (G) \leq 6$ . (Heawood ^{[Heawood 1890]}; Diestel ^{[Diestel 2017 §5.1]}.)

Proof. Both bounds go by induction on the number of vertices $n$ , using that every planar graph has a vertex $v$ with $d (v) \leq 5$ (the light vertex of 40.04.05) and that planarity is hereditary.

Six colours. For $n \leq 6$ assign distinct colours. For $n > 6$ , pick $v$ with $d (v) \leq 5$ . By induction $G - v$ has a proper $6$ -colouring. The vertex $v$ has at most $5$ neighbours, so at most $5$ of the $6$ colours are blocked; give $v$ a free colour. The result is a proper $6$ -colouring of $G$ .

Five colours. For $n \leq 5$ assign distinct colours. For $n > 5$ , pick $v$ with $d (v) \leq 5$ and a proper $5$ -colouring $c$ of $G - v$ . If the neighbours of $v$ use at most $4$ colours, a free colour finishes $v$ . The remaining case is $d (v) = 5$ with the five neighbours $v_{1}, \dots, v_{5}$ in cyclic order around $v$ receiving five distinct colours $1, 2, 3, 4, 5$ . Consider the two neighbours $v_{1}$ (colour $1$ ) and $v_{3}$ (colour $3$ ) and the subgraph $G_{13}$ on colours $1$ and $3$ . Take the $(1, 3)$ -Kempe chain $C$ through $v_{1}$ . If $v_{3} \in / C$ , swap colours $1$ and $3$ throughout $C$ : this keeps the colouring proper and recolours $v_{1}$ to $3$ , so colour $1$ no longer appears among the neighbours of $v$ , and $v$ takes colour $1$ . If instead $v_{3} \in C$ , then a path of alternately $1$ - and $3$ -coloured vertices joins $v_{1}$ to $v_{3}$ ; together with $v$ it bounds a closed region. Because the drawing is planar, this region separates $v_{2}$ from $v_{4}$ , so the $(2, 4)$ -Kempe chain through $v_{2}$ cannot reach $v_{4}$ . Swap colours $2$ and $4$ on the component of $v_{2}$ in $G_{24}$ ; now colour $2$ is absent among the neighbours of $v$ , and $v$ takes colour $2$ . Either way $G$ is properly $5$ -coloured. $□$

Bridge. The five-colour theorem builds toward the four-colour theorem and appears again in the colouring of surfaces, because it shows the light vertex of 40.04.05 plus a single Kempe swap already buys all but one colour. The foundational reason the swap succeeds is planarity itself: the alternating $(1, 3)$ -path and the vertex $v$ enclose a region, and this is exactly the Jordan-curve separation that forbids the $(2, 4)$ -chain from crossing it, so the topology of the plane is what makes the colour bookkeeping close. The two-colour subgraph $G_{ij}$ and its swap generalises the greedy reservation of a colour from 40.04.06 into a global recolouring, and putting these together the entire classical theory becomes the study of when one or two Kempe swaps free a colour. The central insight is that planar sparsity caps the local obstruction at degree five, and the bridge is that the same configuration, a degree-five vertex, is the first case the four-colour discharging argument must still defeat by computer.

Exercises Intermediate+

Exercise 3 (medium, short-answer).

In the five-colour proof, explain precisely why, when the $(1, 3)$ -Kempe chain through $v_{1}$ reaches $v_{3}$ , the $(2, 4)$ -Kempe chain through $v_{2}$ cannot reach $v_{4}$ .

Hint

The $(1, 3)$ -path together with $v$ forms a closed curve. Apply the Jordan curve theorem.

Answer

If the $(1, 3)$ -chain through $v_{1}$ contains $v_{3}$ , there is a path $P$ of alternately $1$ - and $3$ -coloured vertices from $v_{1}$ to $v_{3}$ . Adjoining the two edges $v v_{1}$ and $v v_{3}$ closes $P$ into a cycle $Z$ , drawn without crossings since $G$ is plane. By the Jordan curve theorem $Z$ separates the plane into an inside and an outside. In the cyclic order $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}$ around $v$ , the vertex $v_{2}$ lies on one side of $Z$ and $v_{4}$ on the other, because $v_{1}$ and $v_{3}$ are the endpoints of $Z$ on $v$ . Any $(2, 4)$ -coloured path from $v_{2}$ would have to cross $Z$ to reach $v_{4}$ , but every vertex of $Z$ is coloured $1$ or $3$ , so no such path exists. Hence $v_{4}$ is outside the $(2, 4)$ -chain of $v_{2}$ , and swapping that chain frees colour $2$ at $v$ . Rubric: full credit for the closed curve, the Jordan separation, and the colour-disjointness argument.

Exercise 5 (medium, short-answer).

Show that the map-colouring problem for a bridgeless map reduces exactly to vertex colouring of a loopless planar graph, and explain why bridges must be excluded.

Hint

Build the dual: one vertex per country, one edge per shared border arc. What does a bridge produce in the dual?

Answer

Form the dual $G^{*}$ of the map: place a vertex inside each country and join two vertices by an edge for each border arc their countries share. A proper colouring of the map (adjacent countries differ) is precisely a proper vertex colouring of $G^{*}$ , since adjacency of countries corresponds to edges of $G^{*}$ . The dual is planar because it is drawn with each edge crossing one primal border. A bridge of the map is a border with the same country on both sides; in the dual it becomes a loop at that country's vertex, and a loop makes proper vertex colouring impossible. Excluding bridges (bridgeless maps) makes $G^{*}$ loopless, so the chromatic number is finite and the theorems apply. Rubric: full credit for the dual construction, the colouring correspondence, and the bridge-to-loop observation.

Exercise 7 (hard, short-answer).

Prove that $K_{7}$ embeds on the torus, and deduce that the chromatic number of the torus is at least $7$ , matching the Heawood bound.

Hint

Use Euler's formula on the torus, $n - e + f = 0$ , to check the edge count is feasible, then exhibit an embedding by a rotation scheme or a $7 \times 7$ grid identification.

Answer

On the torus Euler's formula reads $n - e + f = ε = 0$ . For $K_{7}$ , $n = 7$ and $e = (2 7) = 21$ , so a cellular embedding would have $f = e - n = 14$ faces. Each face is bounded by at least $3$ edges and each edge borders two faces, so $3 f \leq 2 e$ , i.e. $42 \leq 42$ , holding with equality; the embedding is a triangulation, which is consistent. An explicit embedding takes the seven vertices as $Z_{7}$ on a flat torus (a square with opposite sides identified) placed so that every difference $1, \dots, 6$ is realised by a straight chord, and the rotation system $i \mapsto (i + 1, i + 2, i + 3, i + 4, i + 5, i + 6)$ gives a triangular embedding (this is the Heffter-Edmonds scheme). Since $K_{7}$ embeds on the torus and $K_{7}$ needs $7$ colours, the torus has chromatic number at least $7$ ; the Heawood bound gives at most $7$ , so it equals $7$ . Rubric: full credit for the Euler-formula feasibility check, an embedding argument, and the chromatic conclusion.

Exercise 8 (hard, short-answer).

Identify the flaw in Kempe's 1879 four-colour argument: it tried to handle a degree-five vertex $v$ whose neighbours use all four colours by performing two Kempe swaps at once. Explain what can go wrong.

Hint

Two Kempe chains in different colour pairs can share vertices and interfere, so swapping one can disrupt the situation that justified swapping the other.

Answer

Kempe considered a degree-five vertex $v$ with neighbours coloured, say, $1, 2, 3, 4, 1$ around $v$ , so two neighbours share colour $1$ and colours $2, 3, 4$ each appear once. To free a colour he proposed swapping a $(2, 4)$ -chain on one side and a $(3, 4)$ -chain on another side simultaneously, aiming to remove both an instance of colour $4$ and free a colour for $v$ . The error is that these two chains can overlap: a vertex can lie on both an $(2, 4)$ -alternating structure and a $(3, 4)$ -alternating structure depending on its colour, and performing the first swap changes which vertices belong to the second chain. After the first swap the configuration that justified the second swap may no longer hold, so the second swap can recreate a conflict, leaving $v$ still surrounded by all four colours. Heawood's 1890 counterexample exhibited a map where Kempe's double swap fails, salvaging only the five-colour theorem, where a single swap at a degree-five vertex always works. Rubric: full credit for identifying the interfering-chains overlap and that a single swap survives.

Advanced results Master

Theorem (four-colour theorem). Every loopless planar graph $G$ satisfies $χ (G) \leq 4$ . (Appel-Haken ^{[AppelHaken 1977]}; Robertson-Sanders-Seymour-Thomas ^{[RobertsonSandersSeymourThomas 1997]}; Diestel ^{[Diestel 2017 §5.1]}.) It suffices to four-colour the maximal planar graphs (triangulations), since every planar graph is a subgraph of one. A configuration is a portion of a triangulation, given by a near-triangulated disc with a specified boundary; it is reducible if no minimal counterexample to the four-colour theorem can contain it, because any four-colouring of the rest extends across it, possibly after Kempe swaps. A set of configurations is unavoidable if every triangulation contains at least one member. The proof exhibits an explicit unavoidable set of reducible configurations: a minimal counterexample would contain a member, but no minimal counterexample can contain a reducible configuration, so none exists. Appel and Haken used $1, 482$ configurations; Robertson, Sanders, Seymour, and Thomas reduced this to $633$ configurations and $32$ discharging rules.

The discharging method. Unavoidability is established by discharging. Assign each vertex $v$ the charge $6 - d (v)$ and each face the charge $6 - 2 ℓ$ where $ℓ$ is its boundary length; in a triangulation Euler's formula forces the total charge to be exactly $12$ , so positive charge is present. Discharging rules move charge between nearby vertices without changing the total, redistributing it so that any vertex left with positive charge sits at the centre of one of the configurations in the chosen set. Since the total stays positive, some configuration must appear, proving the set unavoidable ^{[Diestel 2017 §5.1]}. The verification that each listed configuration is reducible, and that the discharging rules force the set, is the part carried out by computer; the human-checkable skeleton is the charge accounting and the reducibility criteria, while the case enumeration is mechanical.

Theorem (Tait's reformulation). A bridgeless cubic plane graph is $4$ -face-colourable if and only if it is $3$ -edge-colourable. (Tait ^{[Tait 1880]}; West ^{[West 2001 §6.3]}.) The four colours are read as the elements of the Klein four-group $Z_{2} \times Z_{2}$ ; a proper $4$ -face-colouring induces an edge labelling by the difference of the two face colours across each edge, which lands in the three non-zero group elements and is a proper $3$ -edge-colouring at every cubic vertex, and the construction reverses. Thus the four-colour theorem is equivalent to the assertion that every bridgeless cubic plane graph has chromatic index $3$ . Dually, since the difference labelling is a nowhere-zero $Z_{2} \times Z_{2}$ tension, the four-colour theorem is equivalent to every bridgeless planar graph admitting a nowhere-zero $4$ -flow on its dual, the planar case of Tutte's flow conjectures developed in 40.04.09.

Theorem (Heawood bound and Ringel-Youngs). For a closed surface $S$ of Euler characteristic $ε \leq 1$ , the chromatic number satisfies $χ (S) \leq H (ε) = ⌊ \frac{1}{2} (7 + 49 - 24 ε) ⌋$ , and equality holds for every such surface except the Klein bottle, where $χ = 6 < 7 = H (0)$ . (Heawood ^{[Heawood 1890]}; Ringel-Youngs ^{[RingelYoungs 1968]}; Mohar-Thomassen ^{[Mohar-Thomassen 2001 Ch. 8]}.) The upper bound is a short Euler-formula count: a graph embedded on $S$ has a vertex of degree below $H (ε)$ , and induction with that light vertex gives the bound, exactly as in the five-colour proof on the sphere. The hard direction is the lower bound, requiring $K_{H (ε)}$ to embed on $S$ ; Ringel and Youngs settled this by constructing triangular embeddings of complete graphs through twelve cases of current graphs and rotation schemes. The sphere, $ε = 2$ , is the exceptional surface the Heawood formula does not govern, and is precisely where the four-colour theorem rather than five is the truth.

Synthesis. These results are one phenomenon — the chromatic cost of an embedding constraint — read at three depths, and putting these together map colouring becomes the study of how the topology of a surface bounds the chromatic number of the graphs it carries. The foundational reason the six-, five-, and four-colour theorems form a ladder is that each is the same induction on a light vertex, with the Kempe swap closing the gap from six to five and the discharging argument over reducible configurations closing the far harder gap from five to four; this is exactly the principle that planar sparsity localises every obstruction, and the central insight is that the obstruction lives at a degree-five vertex that one swap defeats but a single swap of two chains, as Kempe found, does not. Tait's theorem shows the four-colour theorem is dual to a chromatic-index statement and, through the difference labelling, to a nowhere-zero $4$ -flow, so the colouring of 40.04.06 and the flows of 40.04.09 are two faces of one planar duality. The Heawood-Ringel-Youngs theory generalises the whole ladder off the sphere: the chromatic number of a surface is a floor function of its Euler characteristic, and the sphere's value of four is the lone case the elementary Heawood count cannot reach, the bridge from the easy upper bounds to the computer-assisted summit.

Full proof set Master

Proposition 1 (six-colour theorem). Every loopless planar graph $G$ satisfies $χ (G) \leq 6$ .

Proof. Induct on $n = ∣ V (G) ∣$ . For $n \leq 6$ colour the vertices distinctly. For $n > 6$ , the light-vertex corollary of 40.04.05 supplies a vertex $v$ with $d (v) \leq 5$ . The graph $G - v$ is planar (planarity is hereditary), so by induction it has a proper $6$ -colouring. The neighbours of $v$ number at most $5$ , hence use at most $5$ colours, leaving one of the six free for $v$ . Colouring $v$ with a free colour gives a proper $6$ -colouring of $G$ . $□$

Proposition 2 (five-colour theorem). Every loopless planar graph $G$ satisfies $χ (G) \leq 5$ .

Proof. Induct on $n$ . For $n \leq 5$ colour distinctly. For $n > 5$ , take $v$ with $d (v) \leq 5$ and, by induction, a proper $5$ -colouring $c$ of $G - v$ . If $c$ uses at most $4$ colours on the neighbours of $v$ , extend by a free colour. Otherwise $d (v) = 5$ and the neighbours $v_{1}, \dots, v_{5}$ , in the cyclic order around $v$ , carry the distinct colours $1, \dots, 5$ . Let $G_{ij}$ be induced by the vertices coloured $i$ or $j$ , and let $C_{ij} (u)$ be the component of $u$ in $G_{ij}$ (its Kempe chain). Consider $C_{13} (v_{1})$ . If $v_{3} \in / C_{13} (v_{1})$ , swap colours $1$ and $3$ on $C_{13} (v_{1})$ ; this stays proper, and now $v_{1}$ has colour $3$ , so colour $1$ is absent at the neighbours of $v$ and $v$ takes colour $1$ . If $v_{3} \in C_{13} (v_{1})$ , an alternating $1$ - $3$ path $P$ joins $v_{1}$ to $v_{3}$ ; the cycle $Z = P + v v_{1} + v v_{3}$ is a closed curve, so by the Jordan curve theorem it separates $v_{2}$ from $v_{4}$ . Therefore $C_{24} (v_{2})$ omits $v_{4}$ , since any $2$ - $4$ path from $v_{2}$ to $v_{4}$ would cross $Z$ , whose vertices are all coloured $1$ or $3$ . Swap colours $2$ and $4$ on $C_{24} (v_{2})$ ; now colour $2$ is absent at the neighbours of $v$ , and $v$ takes colour $2$ . In both cases $G$ has a proper $5$ -colouring. $□$

Proposition 3 (dual reduction of map colouring). For a bridgeless map $M$ with dual plane graph $G^ $, t h e l e a s t n u mb er o f co l o u r s f or$ M $e q u a l s$ \chi(G^) $, an d$ G^$ is a loopless planar graph; conversely every loopless planar graph arises this way.*

Proof. By construction the vertices of $G^{*}$ are the countries of $M$ and the edges of $G^{*}$ are the shared border arcs, so a colouring of $M$ with adjacent countries differing is exactly a function on $V (G^{*})$ differing across every edge, a proper vertex colouring. Hence the minimum colour counts coincide. A bridge of $M$ is a border arc with one country on both sides, which would be a loop of $G^{*}$ ; bridgelessness removes loops, so $G^{*}$ is loopless. $G^{*}$ is plane because each dual edge is drawn crossing exactly one primal border. Conversely, a loopless plane graph $H$ is the dual of the map whose countries are the faces of the dual $H^{*}$ , and $(H^{*})^{*} = H$ for connected plane graphs by 40.04.05, so every loopless planar graph is some map's dual. $□$

Proposition 4 (Tait's theorem). A bridgeless cubic plane graph $G$ is $4$ -face-colourable if and only if it is $3$ -edge-colourable.

Proof. Identify the four face colours with the Klein four-group $K = Z_{2} \times Z_{2}$ , with identity $0$ and three non-zero elements $a, b, c$ satisfying $a + b = c$ and $x + x = 0$ . Given a proper $4$ -face-colouring $ϕ$ , label each edge $e$ by $ψ (e) = ϕ (f_{1}) + ϕ (f_{2})$ , where $f_{1}, f_{2}$ are the two faces meeting at $e$ ; since adjacent faces differ, $ψ (e) \neq = 0$ , so $ψ$ takes values in ${a, b, c}$ . At a cubic vertex $v$ the three incident edges separate three faces, whose colours are distinct, so the three labels are the three distinct differences $a, b, c$ — a proper $3$ -edge-colouring. Conversely, given a proper $3$ -edge-colouring $ψ : E \to {a, b, c}$ , the sum of labels around any face boundary is $0$ in $K$ (each of $a, b, c$ appears an even number of times, forced by the cubic structure and parity), so $ψ$ is the coboundary of a face labelling $ϕ$ into $K$ ; adjacent faces receive different colours because the edge between them has non-zero label. Thus the two colourings correspond. $□$

Proposition 5 (Heawood upper bound). For a closed surface $S$ with Euler characteristic $ε \leq 1$ , every graph embeddable in $S$ satisfies $χ \leq H (ε) = ⌊ \frac{1}{2} (7 + 49 - 24 ε) ⌋$ .

Proof. Let $G$ be embedded in $S$ with $n$ vertices and $e$ edges; assume $n \geq H (ε)$ (else colour distinctly). Euler's formula on $S$ gives $n - e + f = ε$ with $3 f \leq 2 e$ , whence $e \leq 3 n - 3 ε$ and the average degree is below $6 - 6 ε / n$ . Solving $H (ε)$ as the larger root of $h^{2} - 7 h + 6 ε = 0$ rounded down, one checks $2 e / n \leq H (ε) - 1$ for $n \geq H (ε)$ , so $G$ has a vertex of degree at most $H (ε) - 1$ . Induction on $n$ : delete such a vertex, colour the rest with $H (ε)$ colours, and re-insert, its at most $H (ε) - 1$ neighbours leaving a colour free. Hence $χ (G) \leq H (ε)$ . $□$

Proposition 6 (torus chromatic number is seven). The torus has chromatic number exactly $7$ .

Proof. The torus has $ε = 0$ , so $H (0) = ⌊ \frac{1}{2} (7 + 7) ⌋ = 7$ , giving $χ \leq 7$ by Proposition 5. For the reverse, $K_{7}$ embeds on the torus: with $n = 7$ , $e = 21$ , a cellular embedding has $f = e - n = 14$ triangular faces ( $3 f = 42 = 2 e$ ), realised by the rotation scheme $i \mapsto (i + 1, i + 2, \dots, i + 6)$ on the vertex set $Z_{7}$ (the Heffter-Edmonds current-graph construction). As $K_{7}$ requires $7$ colours and lives on the torus, $χ (torus) \geq 7$ . Combining, $χ (torus) = 7$ . $□$

Connections Master

Planar graphs, Euler's formula, and the light vertex 40.04.05. The entire ladder of colour bounds runs on the degree-at-most-five vertex proved there: the six- and five-colour inductions remove it and re-insert it, and the four-colour discharging argument assigns charge $6 - d (v)$ so that Euler's formula forces total charge $12$ . Map colouring is the colouring face of the planar structure theory that unit owns, and the dual reduction of a map to a vertex-colouring problem is built on the planar duality defined upstream.
Vertex colouring, Brooks' theorem, and the chromatic polynomial 40.04.06. This unit is the planar specialisation of the general chromatic theory: $χ (G) \leq 4$ for planar $G$ is the sharpest possible degree-independent bound, far below the general $χ \leq Δ + 1$ , and Birkhoff introduced the chromatic polynomial precisely to attack the four-colour theorem by proving $P (G, 4) > 0$ . The Kempe-chain swap is a global version of the colour-reservation that drives the greedy and degeneracy bounds there, and the four-colour theorem is the assertion that the chromatic polynomial of every planar triangulation is positive at four.
Network flows and nowhere-zero flows 40.04.09. Tait's theorem recasts the four-colour theorem as the three-edge-colourability of bridgeless cubic plane graphs, and through the Klein-four-group difference labelling as the existence of a nowhere-zero $4$ -flow on the dual; the four-colour theorem is thus the planar case of Tutte's nowhere-zero-flow conjectures developed there. The duality between tensions (colourings) and flows on a planar graph is the structural reason map colouring and flow theory are the same subject on the sphere.
The graph-minor theorem and Hadwiger's conjecture 40.04.10. Hadwiger's conjecture — that a graph with no $K_{t}$ minor is $(t - 1)$ -colourable — has its case $t = 5$ equivalent to the four-colour theorem, since by Wagner's structure theorem the $K_{5}$ -minor-free graphs are built by clique-sums from planar pieces and the Wagner graph. The four-colour theorem is therefore the first deep instance of the minor-to-colouring principle that the graph-minors unit develops, and Hadwiger's conjecture is its conjectural generalisation to all $t$ .

Historical & philosophical context Master

The four-colour problem was posed by Francis Guthrie in 1852 and transmitted through Augustus De Morgan; Arthur Cayley revived it in 1878. Alfred Kempe published a proof in 1879 in the American Journal of Mathematics (volume 2) ^{[Kempe 1879]}, introducing the chain-and-swap argument that bears his name. Percy Heawood found the fatal flaw in Kempe's double-swap step in 1890, in Map-colour theorem (Quarterly Journal of Pure and Applied Mathematics 24) ^{[Heawood 1890]}, where he salvaged the five-colour theorem and proved the general upper bound $H (ε)$ for surfaces of positive genus, conjecturing it to be exact. Peter Guthrie Tait gave his edge-colouring reformulation in 1880 (Transactions of the Royal Society of Edinburgh 29) ^{[Tait 1880]}.

The exactness of Heawood's bound was established for the orientable surfaces by Gerhard Ringel and J. W. T. Youngs in 1968 (Proceedings of the National Academy of Sciences 60) ^{[RingelYoungs 1968]}, completing the twelve-case current-graph computation that constructs triangular embeddings of complete graphs; the Klein bottle is the sole surface where the bound is not attained, a fact Franklin had settled in 1934. The four-colour theorem itself was proved by Kenneth Appel and Wolfgang Haken in 1976, published in 1977 (Illinois Journal of Mathematics 21) ^{[AppelHaken 1977]}, by reducing it to the computer verification of $1, 482$ reducible configurations forming an unavoidable set. A streamlined and independently verified proof with $633$ configurations was given by Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas in 1997 (Journal of Combinatorial Theory Series B 70) ^{[RobertsonSandersSeymourThomas 1997]}, and Georges Gonthier produced a fully machine-checked formalisation in the Coq proof assistant in 2005.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{MoharThomassen2001,
  author    = {Mohar, Bojan and Thomassen, Carsten},
  title     = {Graphs on Surfaces},
  publisher = {Johns Hopkins University Press},
  year      = {2001}
}

@article{Kempe1879,
  author  = {Kempe, Alfred B.},
  title   = {On the geographical problem of the four colours},
  journal = {American Journal of Mathematics},
  volume  = {2},
  year    = {1879},
  pages   = {193--200}
}

@article{Heawood1890,
  author  = {Heawood, Percy J.},
  title   = {Map-colour theorem},
  journal = {Quarterly Journal of Pure and Applied Mathematics},
  volume  = {24},
  year    = {1890},
  pages   = {332--338}
}

@article{Tait1880,
  author  = {Tait, Peter G.},
  title   = {Note on a theorem in geometry of position},
  journal = {Transactions of the Royal Society of Edinburgh},
  volume  = {29},
  year    = {1880},
  pages   = {657--660}
}

@article{AppelHaken1977,
  author  = {Appel, Kenneth and Haken, Wolfgang},
  title   = {Every planar map is four colorable},
  journal = {Illinois Journal of Mathematics},
  volume  = {21},
  year    = {1977},
  pages   = {429--567}
}

@article{RingelYoungs1968,
  author  = {Ringel, Gerhard and Youngs, J. W. T.},
  title   = {Solution of the Heawood map-coloring problem},
  journal = {Proceedings of the National Academy of Sciences},
  volume  = {60},
  year    = {1968},
  pages   = {438--445}
}

@article{RobertsonSandersSeymourThomas1997,
  author  = {Robertson, Neil and Sanders, Daniel and Seymour, Paul and Thomas, Robin},
  title   = {The four-colour theorem},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {70},
  year    = {1997},
  pages   = {2--44}
}

@article{Gonthier2008,
  author  = {Gonthier, Georges},
  title   = {Formal proof---the four-color theorem},
  journal = {Notices of the American Mathematical Society},
  volume  = {55},
  year    = {2008},
  pages   = {1382--1393}
}

Prerequisites

40.04.05
40.04.06

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1 (the four- and five-colour theorems, map colouring) read for the map-and-dual pictures; Wilson 2002 *Four Colors Suffice* (Princeton) Ch. 1-3 for the history and the bare map-colouring problem; 3Blue1Brown / Numberphile's four-colour-theorem essay for the country-to-dot reduction
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1 (the six-colour and five-colour theorems with the Kempe-chain proof, the four-colour theorem stated); West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §6.3 (map colouring, the five-colour theorem, Kempe chains, Tait's theorem); Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) §11.1-§11.3
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §5.1 and the discharging discussion; Mohar-Thomassen 2001 *Graphs on Surfaces* (Johns Hopkins) Ch. 8 (colouring graphs on surfaces, the Heawood number, the Ringel-Youngs theorem); Robertson-Sanders-Seymour-Thomas 1997 (the modern four-colour proof and discharging); the original sources Heawood 1890, Kempe 1879, Appel-Haken 1977, Tait 1880, Ringel-Youngs 1968

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, §5.1 (the colouring of plane graphs: the six-colour theorem, the five-colour theorem via Kempe chains, the four-colour theorem and the discharging method, and the dual reformulation of map colouring as vertex colouring)
West 2001 — Introduction to Graph Theory (2nd edition) · Prentice Hall, 2001, §6.3 (map colouring, the dual graph, the five-colour theorem with the full Kempe-chain argument, Kempe's flawed proof, and Tait's theorem relating four-colourings to three-edge-colourings of bridgeless cubic planar graphs)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, §11.1-§11.3 (planar colourings, the five-colour theorem, the four-colour theorem, nowhere-zero flows and Tait colourings)
Mohar, Thomassen 2001 — Graphs on Surfaces · Johns Hopkins University Press, 2001, Ch. 8 (the chromatic number of surfaces, the Heawood bound, and the Ringel-Youngs theorem giving equality for every surface except the Klein bottle)
Heawood 1890 — Map-colour theorem · Quarterly Journal of Pure and Applied Mathematics 24 (1890) 332-338; the correction of Kempe's proof, the five-colour theorem, and the Heawood upper bound for surfaces of positive genus
Kempe 1879 — On the geographical problem of the four colours · American Journal of Mathematics 2 (1879) 193-200; the Kempe-chain method and the flawed four-colour proof
AppelHaken 1977 — Every planar map is four colorable · Illinois Journal of Mathematics 21 (1977) 429-567 (Part I, discharging) and 491-567 (Part II, reducibility); the computer-assisted proof via an unavoidable set of reducible configurations
Tait 1880 — Note on a theorem in geometry of position · Transactions of the Royal Society of Edinburgh 29 (1880) 657-660; the equivalence of the four-colour theorem with the three-edge-colourability of bridgeless cubic planar graphs
RingelYoungs 1968 — Solution of the Heawood map-coloring problem · Proceedings of the National Academy of Sciences 60 (1968) 438-445; the genus computation establishing equality in the Heawood bound for all orientable surfaces
RobertsonSandersSeymourThomas 1997 — The four-colour theorem · Journal of Combinatorial Theory Series B 70 (1997) 2-44; the streamlined discharging proof with 633 reducible configurations and 32 discharging rules

Estimated time

beginner: 18m
intermediate: 46m
master: 88m