Seven regions on a doughnut

On a torus, seven colours are sometimes necessary and always sufficient. Both halves were settled by Percy Heawood in 1890, eighty-six years before the plane’s four, and the necessary half is a single picture.

Every pair of those seven regions shares a border. So no two may take the same colour, and seven colours are needed. That is the whole of the lower bound, and it fits in a drawing.

A statement of that shape is worth distinguishing from the theorem it supports. The picture shows that seven are sometimes necessary; it says nothing about whether seven are always enough, which is a separate argument given below. Most of the difficulty in this subject lives in the second kind of claim, and most of the pictures answer the first.

Why the pattern works #

The bricks are labelled so that stepping one place right adds $1$ to the label and stepping one row up adds $3$, both counted modulo seven.

Because each row is offset by half a brick, a brick touches two bricks in the row above and two in the row below, not one. Those four neighbours have labels differing by $3$, by $3-1 = 2$, by $-3$ and by $-2$. Together with the two side neighbours at $\pm1$, the differences are

$$\pm 1, \pm 2, \pm 3,$$

which is every non-zero residue modulo seven. So each region borders every other, and the adjacency graph is the complete graph on seven points.

The generator checks that rather than describing it: it walks every brick in the pattern, records which labels meet along a border of positive length, and refuses to draw unless all twenty-one pairs are present.

That $K_7$ can be drawn on a torus without crossings is the whole content, and it is the point where this rung meets the graph that cannot be drawn in the plane: $K_5$ already fails there, and a torus accommodates $K_7$ comfortably.

The bound, from the characteristic #

The other half — that seven is always enough — is a counting argument of the same kind as the five-colour proof, run on a surface where the arithmetic gives a different answer.

On a surface of Euler characteristic $\chi$, the same face-counting that gives $E \le 3V - 6$ in the plane gives $E \le 3V - 3\chi$. The average degree is therefore below $6 - 6\chi/V$, and on a torus, where the characteristic is zero, that is below $6$ — so some vertex has degree at most $6$, and a greedy argument colours the graph with seven.

Heawood ran the same computation for every surface and obtained

$$H(\chi) = \left\lfloor \frac{7 + \sqrt{49-24\chi}}{2} \right\rfloor,$$

which is $7$ at $\chi = 0$, $8$ for a two-handled surface, $9$ for three handles, and $38$ at a hundred. He proved the bound and believed he had proved it attained; the second half of his paper had a gap, and the statement that every surface has a map actually needing $H(\chi)$ colours was not settled until Ringel and Youngs in 1968, by an argument that constructs the maps case by case.

The same seven, counted a different way #

There is a second way to see that seven is exactly right on a torus, and it uses nothing but the characteristic.

Suppose a map on the torus has $n$ regions, every pair of which share a border. Then its adjacency graph is $K_n$ drawn on the torus, and the counting that produced the bound gives $E \le 3V$ — here $\binom{n}{2} \le 3n$, so $n \le 7$.

So no eight regions on a torus can all touch, which is the upper bound’s content in its sharpest form — and the brick pattern shows seven that do. The two meet with nothing between them.

The same inequality on the sphere, where $\chi = 2$, gives $\binom{n}{2} \le 3n - 6$, so $n \le 4$: at most four regions on a plane or sphere can mutually touch. That is a complete proof that four colours are sometimes necessary — and it says nothing whatever about whether four are sufficient, which is the whole difficulty. On the torus the two questions have the same answer; in the plane they do not, and the gap between four regions can all touch and four colours always suffice is where the century went.

Why the harder surface is the easier problem #

The plane’s case is the exception in this family, and the reason is that its bound has no slack.

Substituting $\chi = 2$ into Heawood’s formula returns $4$ — the correct answer — but the derivation is invalid there, because the step that turns the degree bound into a colouring needs $\chi \le 0$. What the counting actually delivers in the plane is $6$, improved to $5$ by a Kempe chain, and the last step from five to four is not available to any counting argument at all.

On a torus the counting gives $7$ and the construction needs $7$: the two meet exactly, so nothing is left to prove. On a surface with a hundred handles the counting gives $38$ and a map needing $38$ exists. It is only on the simplest surface of all that the easy bound and the truth differ, and the gap is precisely the eighty-six years.

There is one further exception and it is stranger. The Klein bottle has $\chi = 0$, exactly like the torus, so Heawood’s formula predicts seven — and the true answer is six, proved by Franklin in 1934. Out of an infinite family, exactly one surface disobeys a formula that holds everywhere else, and it is not the one anybody would have picked.

What the construction really produces #

Seen from the graph’s side, the picture is an embedding of $K_7$ in the torus, and that is the form in which the result generalises.

The minimum number of handles a surface needs to carry $K_n$ without crossings is its genus, and Ringel and Youngs computed it:

$$g(K_n) = \left\lceil \frac{(n-3)(n-4)}{12} \right\rceil.$$

At $n=5$ and $n=6$ that is $1$: neither fits in the plane and both fit on a torus. At $n=7$ it is still $1$, which is exactly what the brick pattern shows. At $n=8$ it becomes $2$, so eight mutually bordering regions need a two-handled surface — and the Heawood bound for that surface is $8$, which is why the two results are the same theorem.

That correspondence is what makes the colouring problem on surfaces tractable. The question how many colours does this surface need becomes how large a complete graph does this surface hold, which is a question about embedding rather than about colouring, and embeddings can be constructed and counted.

Heawood, twice #

Percy Heawood appears twice in this ladder and it is the same 1890 paper both times.

That paper does three things. It finds the flaw in Kempe’s eleven-year-old proof of the four-colour theorem; it salvages the method as the five-colour theorem; and it computes the bound for every other surface. The third part is why the subject’s results on complicated surfaces predate its result on the simplest one — Heawood had them all in one go, while the plane was left open by the same paper.

He also believed he had proved the bound attained on every surface, and that half of the paper is wrong. The error was noticed by Heffter in 1891, who verified the construction for the first few surfaces and could not complete the general case. The gap stayed open until 1968, when Ringel and Youngs closed it by building the required maps in twelve separate cases according to the genus modulo twelve — with the last one, curiously, completed only after the rest, and the Klein bottle standing outside the whole scheme as the single exception.

Seventy-eight years is a long time for a statement everybody believed, and the shape of the eventual proof — a dozen cases, each with its own construction — is a reminder that a formula holding for every surface does not imply a single argument covering every surface.

What it costs #

The construction gives seven and gives nothing about which maps actually need it.

Almost every map on a torus is four-colourable or five-colourable; the seven-region pattern is a special arrangement, and a randomly drawn map on a torus will not resemble it. The theorem is about the worst case, and the worst case here is a single well-chosen picture rather than a typical object.

There is also nothing algorithmic in it. Deciding whether a given toroidal map needs six colours or five is not made easier by knowing that seven always suffice, and the corresponding decision problems remain hard. Sufficiency proofs of this kind bound the answer and say nothing about computing it, which is the same limitation the four-colour theorem has: a planar map is four-colourable, and finding the colouring is a separate piece of work.

Building the pattern by hand #

The brick construction is worth being able to reproduce, because it is short and because the same recipe gives the maps on other surfaces.

Take a rectangle seven bricks wide. Label the bricks of the bottom row $0$ to $6$ from left to right. Shift the next row half a brick to the right and label it so that each brick’s number is three more than the one below and to its left, modulo seven. Repeat. Glue the left edge to the right and the top to the bottom.

The step of three is not a free choice, and the generator is the thing that establishes it. A step of two gives vertical neighbours differing by two and diagonal ones differing by one, so the differences available are only $\pm1$ and $\pm2$: fourteen of the twenty-one pairs touch and seven do not. The figure refuses to draw it — the assertion counts the pairs and finds fourteen where twenty-one were claimed — which is what a checked figure is for. A step of four fails the same way, leaving the pairs at distance two apart untouched.

So exactly one step works, and the reason is arithmetic: the differences generated are $1$, the step, and the step minus one, and only $\{1, 2, 3\}$ covers every residue modulo seven once negatives are included.

What matters is the arithmetic rather than the drawing. The pattern is a statement about $\mathbb{Z}_7$ — that $\{\pm1, \pm2, \pm3\}$ exhausts the non-zero residues — dressed up as a tiling, and the tiling is planar-looking because the torus is what a repeating pattern with two directions of repetition lives on.

Where it needs a condition #

Every region in the brick pattern is a single connected piece, and that condition is doing as much work here as it does in the plane. Allowing a country made of two disconnected pieces that must share a colour breaks the bound on any surface.

The regions must also be discs — each one bounded by a single closed curve, with no handle running through it. A region that wraps all the way round the torus is not a disc, and the face-counting behind Heawood’s bound assumes every face is one, exactly as the cell-decomposition condition in the characteristic’s general statement does. The bricks in the figure satisfy this: each is a small rectangle, and it is the pattern that wraps rather than any single region.

And the identification has to be the torus’s own. Gluing the rectangle’s edges with a flip rather than a straight translation gives a Klein bottle, the same $\chi = 0$, and the answer six rather than seven — so the surface is not determined by the characteristic alone, and the drawing’s arrows are part of its content rather than decoration.

What the picture cannot show #

The rectangle is not the surface. It is a rectangle, and the reader is asked to remember that its opposite edges are the same edge — which is a fact carried by two lines of text and by nothing in the drawing.

That matters because most of the adjacencies the theorem needs are across those edges. Two regions that touch only after the identification look, on the page, like two regions at opposite ends of a rectangle with several others between them. Every claim of the form region 2 borders region 5 has to be checked by wrapping, and the drawing offers no help; the generator does the check, on the pattern’s own arithmetic, and refuses to draw unless all twenty-one pairs are found.

There is also no honest picture of the torus itself here. Drawing the brick pattern on a doughnut in perspective would show perhaps half the regions, with the rest hidden behind, and the ones that matter — the pairs that touch only through the identification — would be exactly the ones out of sight. The flat rectangle with arrows is the standard compromise, and it trades a true picture of the surface for a legible picture of the pattern.

The ladder from here #

Below: the four-colour theorem, the five-colour argument and the polynomial that counts colourings. Sideways: the Euler characteristic that supplies the bound, the classification of surfaces that says which surfaces there are to ask about, and the genus of a complete graph, which is the same result in the language of embeddings.

The simplest case is not the easiest #

The lasting point is the inversion at the centre of this rung.

The plane is the simplest surface there is. Its colouring problem was the last to be settled, took a century, and required a computer. The torus, the Klein bottle, the two-handled surface and the surface with a hundred handles were all settled by hand, and the harder the surface looks, the more comfortably the argument closes.

The reason is slack. On a complicated surface the counting bound is generous enough for a clean argument to reach it, and a construction exists to meet it from below. On the plane the bound and the truth are one apart, and there is nothing left over to spend.

That pattern is worth expecting rather than being surprised by. The last case of Fermat’s Last Theorem to feel elementary was the first to be proved; small cases of conjectures are routinely checked by exhaustion because the general argument has run out of room exactly there. Simplest and easiest are different words, and where a general method has margin, the special case where it has none is the one that will hold out.