Five colours, and a chain that can be followed

Four colours suffice for any map, and the proof cannot be read by a human being. Five colours also suffice, and that proof is a page long, uses nothing but counting, and can be followed to the end in an afternoon.

The gap between the two is the most instructive thing in the subject, and this essay is about the argument that closes the easy one — because it is also, almost exactly, the argument that appeared to close the hard one for eleven years.

Two facts to start from #

The first is a counting fact. Every planar graph has a vertex with five or fewer neighbours.

That comes straight from Euler’s formula. In a planar graph where every face is bounded by at least three edges, counting the face-edge incidences gives $2E \ge 3F$, and substituting into $V - E + F = 2$ gives $E \le 3V - 6$. The sum of all the degrees is $2E \le 6V - 12$, so the average degree is under six, so some vertex has degree five or less. No graph escapes it.

The second is the shape of the argument. Take a smallest graph that cannot be five-coloured; find a vertex $v$ of degree at most five; delete it. What is left is smaller, so it can be five-coloured. Put $v$ back and try to give it a colour.

If $v$ has four or fewer neighbours, or five neighbours using four or fewer colours between them, a colour is spare and the job is done. The only difficulty is a vertex of degree exactly five whose five neighbours carry five different colours.

The chain #

Pick two of the five neighbours — say the ones coloured $0$ and $2$ — and look at the part of the graph reachable from the first by walking only through vertices coloured $0$ or $2$. That set is a Kempe chain, and the whole trick is that its colours can be swapped wholesale: exchange $0$ and $2$ throughout the chain and the colouring is still proper, because every edge leaving the chain goes to a vertex coloured neither $0$ nor $2$, and swapping two colours that the neighbour does not have cannot create a clash.

If that chain does not reach the neighbour coloured $2$, the swap turns the neighbour coloured $0$ into a $2$, and now no neighbour is $0$, and $v$ takes colour $0$.

The figure’s generator does not take that on trust. It floods the chain from the starting neighbour, checks that the resulting colouring has no edge joining two equal colours, and refuses to draw if any step is not what the caption says it is.

When the chain does reach #

The chain might reach. Then swapping it recolours the far neighbour as well and nothing is freed.

Here is where planarity earns its keep. If the $0$–$2$ chain runs from one neighbour of $v$ all the way to another, then together with $v$ it encloses a closed curve — and the other two neighbours, coloured $1$ and $3$, are separated by it: one inside, one outside.

A $1$–$3$ chain joining them would have to cross that curve. In a planar drawing, crossing means meeting at a vertex, and a vertex on both chains would have to be coloured $0$ or $2$ and $1$ or $3$. There is no such vertex. So the $1$–$3$ chain cannot connect the two, its swap is available, and colour $1$ is freed.

One of the two swaps always works. That is the five-colour theorem, and it is complete.

The argument is finite in a way worth noticing: it examines one vertex, at most two chains, and nothing else. There is no case analysis to exhaust and no configuration to enumerate, which is precisely what a reader can check and what the four-colour proof gave up.

Kempe’s mistake, exactly #

Alfred Kempe published this argument in 1879 — for four colours — and it was accepted as a proof for eleven years.

The four-colour version has to handle the same degree-five vertex, but now with only four colours available, and the hard case is a vertex whose five neighbours use four colours with one repeated. Kempe’s move was to perform two chain swaps, one after another, to free a colour.

Percy Heawood found in 1890 that the two swaps interfere. Each is valid on its own; performing the first changes the graph the second is evaluated on, and Heawood produced a configuration in which the second swap undoes part of the first, leaving a clash that was not there before. The published proof had a hole in a case that nobody had checked by drawing it.

What Heawood salvaged is precisely this essay. The single-swap argument is airtight, it needs five colours rather than four, and Heawood published it as the five-colour theorem in the same paper that demolished the four. That is an unusually clean outcome for a refutation: the method survived, its reach was measured honestly, and the reduced claim has never been in doubt since.

The eleven years are worth dwelling on. The argument is short, it was read by the best people in the subject, and the failure is in a case analysis nobody carried out exhaustively — which is exactly the kind of error a computer does not make and a human reliably does. The proof that eventually settled four colours checks 1,834 configurations by machine, and the usual complaint about it is that no person can read it. The complaint has to be weighed against what happened the last time a person could.

What the counting gives, and where it stops #

The counting argument gives five and cannot be pushed to four.

The gap is not a matter of effort. The counting says a planar graph has a vertex of degree five or less, and a degree-five vertex is exactly the case that the single-swap trick cannot always resolve with four colours. To get four, the argument must handle configurations rather than single vertices — a set of local patterns, at least one of which must appear in any planar graph, each of which can be shown reducible — and the smallest known unavoidable set of reducible configurations has hundreds of members.

That is the whole distance between the two theorems: one vertex against hundreds of configurations, one page against a machine.

The bound the counting gives on its own #

Before any chain swapping, the degree bound alone gives a colouring, and it is worth seeing how far that gets, because it explains why five is the natural stopping place.

Order the vertices by repeatedly removing one of degree five or less; colour them in the reverse of that order, giving each vertex any colour not already on its neighbours. When a vertex is coloured, at most five of its neighbours are already coloured, so six colours always suffice. That is the six-colour theorem, and it needs no chains at all — three lines, given Euler.

Getting from six to five is exactly one Kempe swap. Getting from five to four is the eighty-six years. The sequence of costs — three lines, one page, a machine — is a fair description of how the difficulty is distributed, and none of it was apparent in advance.

It is also worth noting what these arguments never use. Nothing above cares what the map looks like, how many regions it has, whether the borders are straight, or whether the countries are connected — only which regions touch which. The map has been thrown away and the graph kept, and every theorem here is about the graph.

What it costs #

The proof is an induction on the number of vertices, and inductions of this kind are constructive in principle and useless in practice.

Unfolded, the argument gives an algorithm: find a vertex of degree $\le 5$, remove it, colour the rest recursively, put it back and perform up to two chain swaps. That runs in quadratic time and colours any planar graph with five colours, and it is genuinely used.

What it does not give is any information about four. The induction has no way to notice that four would have sufficed, and no version of it that has ever been found gives the better bound. A proof technique that is airtight and cannot be sharpened is a specific kind of dead end, and recognising one early is worth as much as a proof.

Where it needs a condition #

Planarity, in two separate places, and it is worth separating them because they fail differently.

The counting fact — some vertex has degree five or less — needs $E \le 3V - 6$, which is a planarity consequence. On a torus the bound is $E \le 3V$, and the minimum degree can be six.

The crossing argument — two chains cannot both connect — needs a closed curve in the plane to separate inside from outside, which is the Jordan curve theorem. On a torus a closed curve need not separate anything, so two chains can connect, and both swaps can fail at once.

Both failures are real rather than technical, and both are why the torus needs seven colours rather than five. Neither half of the argument survives the change of surface, and it is instructive that the harder surface is the one where the result is easier to prove.

Two further conditions are hidden in the phrase any map, and both have bitten people.

A country made of two disconnected pieces that must take the same colour breaks the theorem outright: with enough such countries, any number of colours can be forced. The four-colour theorem is about maps whose regions are each connected, and the real world — with its exclaves and enclaves — is not such a map.

And a map is not quite a planar graph. Four regions meeting at a single point are not neighbours in the sense the theorem means, since they share no border of positive length; treating a point of contact as adjacency would make the four-colour statement false at once, and the standard counterexample is a pie cut into five slices.

What the picture cannot show #

The figures draw a graph with eight vertices. The theorem is about all planar graphs, and the induction’s force comes from a hypothetical smallest counterexample — an object that does not exist, whose properties are being derived in order to obtain a contradiction.

Nothing here draws that. The wheel is a stand-in: it exhibits the hard local configuration and shows the swap working on it, and it says nothing about whether some other graph might present the configuration in a way the swap cannot handle. The proof that no such graph exists is the argument in prose, not the picture.

The blocked case is worse in an interesting way. Its figure shows a chain that connects and a second chain that does not, in one particular graph. The claim needed is that the second chain can never connect once the first does, which is about every configuration at once, and the picture illustrates the conclusion rather than establishing it. The establishing is done by the separation argument, which is a fact about curves in the plane, and there is no drawing of it that is not simply a drawing of one curve.

What a chain swap really is #

The swap deserves one more paragraph, because the same device turns up far from map colouring and is easier to recognise once named.

A Kempe chain is a connected component of the subgraph induced by two colour classes. Swapping it is an operation on the set of proper colourings rather than on the graph: it takes one valid colouring to another, it is its own inverse, and it changes as little as possible while changing something. That is an involution on the solution space, and the argument uses it to move from a colouring that does not extend to one that does.

Arguments of this shape recur wherever a solution has to be adjusted rather than rebuilt. An augmenting path in a matching problem is the same idea — a two-class alternating structure, flipped along its length, taking one matching to a better one. So is the alternating path in the stable-marriage algorithm, and so is the cycle-cancelling step in a flow problem. In each case the point is that the local change is safe: it can only affect vertices inside the structure, because the boundary was chosen so that nothing outside can notice.

That safety is the property to look for. A modification that might break something elsewhere needs a global check every time it is applied; one whose effects are provably confined to a component can be applied blindly, and an induction can be built on it.

The ladder from here #

Below: the theorem itself. Above: counting the colourings rather than finding one, and the map on a doughnut where seven are needed — where the counting bound is attained and the construction is a picture.

Sideways: the degree bound comes from Euler’s formula, the crossing argument is planarity used as a hypothesis rather than as a curiosity, and the same chain-swapping move reappears in edge colouring, where Vizing’s theorem bounds the number of colours needed for edges by the maximum degree plus one.

A proof’s reach is worth measuring #

The lasting point is not the theorem but what happened to it.

Kempe’s argument was correct machinery aimed one step too far. The chain swap works; two chain swaps interfere; and the difference between those two sentences was invisible for eleven years to everyone who read the paper, including the author. What Heawood did was not find a better method — he found the exact distance the existing one could carry, and stated the theorem that distance supports.

That is a more common outcome in mathematics than the histories suggest, and it is worth doing deliberately: when an argument nearly works, the useful question is not how to force it but what weaker statement it proves cleanly. The weaker statement is often the durable one. Five colours has never needed revising; four took another eighty-six years and a machine.