Four colours, and what a cut cannot do to them

Four rungs of this ladder establish what a projection must give up: continuity or injectivity, a place where north is not up, a pair of antipodes glued together, a degree that counts. All four are about the map.

This one is about the thing every reader thinks a map is for — telling one region from its neighbour — and the theorem that governs it is the most famous statement about maps that anybody has ever proved.

The partition, and the four that are necessary #

The regions here are the ground nearest each of a set of stated places — a spherical Voronoi partition, built from stated sites rather than from a coastline dataset, for the reason this collection made early and has kept.

Four suffice because the adjacency graph of a partition of the sphere into simply connected regions is planar — draw a vertex in each region and an edge across each shared boundary, and no two edges cross — and the four-colour theorem says a planar graph needs at most four. On every partition tried here, from eight regions to thirty, four are also necessary: three never suffice.

The exactness matters for what follows. A greedy colouring can use five where four would do, so a measurement of “how many colours does this map need” has to be a search rather than an algorithm, and it is one: the chromatic number here is found by backtracking over every assignment with the relabellings quotiented out.

The cut, and the guess it invites #

Every projection removes a set — that is rung 1’s whole finding — and for most of the library the set is a half-meridian. Flattening the sphere along it splits every region the meridian crosses into two pieces, one against each edge of the sheet.

Six of the fourteen. Twenty faces where there were fourteen regions.

The guess this invites is well known and is usually stated as an aside in every account of the four-colour theorem: the theorem requires each country to be connected, and a country in two pieces breaks it. The classical counterexample is a ring of countries each with a piece inside a common host, which needs as many colours as there are countries.

A map cut at the antimeridian has six countries in two pieces. Surely it needs more than four.

It needs four, and the reason is one line #

It needs four, and here is why.

The two pieces of a split region, taken together, touch exactly what the region touched on the globe. Nothing was added: the seam runs through the region, not between it and a neighbour, so no new adjacency was created. And nothing was lost that matters to the colouring, because identifying the two pieces restores every adjacency the cut suspended.

So the graph that has to be coloured — faces, with each region’s pieces required to share a colour — is the contracted graph, and contracting the pieces of each region gives back the sphere’s own adjacency graph. Edge for edge.

A cut adds faces and adds no edges, and colouring is a question about edges.

It is worth noticing what the face count does do. Twenty faces from fourteen regions is a forty-three per cent increase in the number of polygons a renderer has to draw, and every one of the six extra ones exists only because of where the seam was put. That is a real cost, paid by every pipeline that stores a world map as drawn polygons, and it is the cost the antimeridian is a cut in the numbers prices from the other side.

That is a stronger statement than a measurement, because it holds for every projection and every seam: whatever a projection removes, the pieces of a region are still the region, and a map of the world in any projection needs the colours the globe needed.

The seam, as this ladder already had it #

The seam is a set of measure zero and it is not nothing: it is the exact set on which injectivity fails, and its page length is what the projection paid to be continuous everywhere else. What this rung adds is that the price is paid in ink rather than in structure. A duplicated curve costs a reader a discontinuity to look at and costs the map’s combinatorics nothing at all.

That distinction runs through the whole ladder in retrospect. The removed set has a dimension, a length and a place, all of which rung 1 measures, and it has a degree, which rung 4 measures. It does not have an effect on any property computed from adjacency, and that absence had never been stated.

How many regions a seam splits, and how that scales #

The face count is the one quantity the cut does move, and the five partitions give it a law.

The splits run 4, 5, 6, 6 and 8 against region counts of 8, 12, 14, 20 and 30, and dividing each by the square root of its region count gives 1.41, 1.44, 1.60, 1.34 and 1.46. So

$$\text{regions split} \approx 1.45\sqrt{n},$$

which is what a curve of fixed length crossing a partition into n cells has to do: a cell’s linear size falls as 1/√n, so a seam of fixed length meets proportionally more of them, and the count rises as the square root rather than in proportion.

The consequence is that the fraction split falls as 1/√n. Half the regions at eight, forty-three per cent at fourteen, twenty-seven at thirty — and about ten per cent at two hundred, which is the number of countries on a world map. Against the antimeridian that is roughly the two dozen states with territory on both sides of it, which is the right order.

That is worth stating because the essay’s own forty-three per cent is a small-partition figure and reads as a general one. The rendering overhead a seam imposes is not forty-three per cent; it is 1.45/√n, and on any partition fine enough to be worth drawing it is a few per cent. A world map of countries pays ten; a map of a country’s own municipalities pays two or three; a raster tile scheme, whose cells are far finer, pays a fraction of one.

And the direction is the reassuring one. The finer the partition, the less the seam costs in faces — while the colouring result says it costs nothing in colours at any size. Both of the cut’s consequences improve as the map gets more detailed, which is the opposite of most of the costs this collection measures and is worth noticing for that reason alone: it is the rare case where refinement is on the reader’s side.

What does cost a fifth colour #

The exclave objection is right about exclaves and wrong about cuts, and the difference is worth measuring rather than asserting.

An exclave adds edges. A region with a piece inside a distant host becomes adjacent to everything the host touches, and to every other exclave in the same host — so k exclaves in one host form a clique of size k, and a clique of size k needs k colours. The bound is unbounded.

The distinction is between a region that is disconnected on the sphere and one that is disconnected on the page. The first is a fact about the world and costs colours without limit. The second is a fact about the projection and costs nothing.

The three cases, separated #

The confusion this rung exists to clear up is between three different things that all look like a country in two pieces.

A country the projection split. Two faces on the page, one region on the globe. Costs nothing: identifying the faces gives back the sphere’s graph.

A country with a genuine exclave. Two regions on the globe, one country. Costs colours without limit, because it manufactures adjacency between things that do not touch.

A country with an enclave inside it — a neighbour entirely surrounded. One region with a hole. Costs nothing either, and for a different reason: the enclave is adjacent to exactly one thing, so it takes any colour but its host’s.

Only the middle case is a problem, and it is the only one of the three that is a fact about the world rather than about the drawing. A reader who knows the theorem and sees a split country on an atlas page has met the first case and is thinking about the second.

Where a real map-colouring program goes wrong #

The theorem is safe and the practice is not, and the gap between them is where this rung earns its place on a ladder about projections.

An automatic colourer works on the drawn faces, because that is what a rendering pipeline has. Handed a cut sheet it sees twenty polygons, not fourteen regions, and it will happily give the two pieces of a split country different colours — a country blue on the left edge of the sheet and green on the right, which is a defect a reader notices immediately and which no colouring check would catch, because the colouring is valid on the faces.

Worse, it may use fewer colours than the map needs. Cutting suspends the adjacencies that crossed the seam, so the face graph is a subgraph of the contracted one — genuinely easier to colour — and a program that reports “three colours sufficed” has reported a fact about a sheet rather than about the world.

The repair is the same one this collection keeps arriving at: do the topology on the sphere and the drawing on the page. The antimeridian is a cut in the numbers makes the point for a bounding box, a polygon on a sphere has no outside makes it for containment, and here it is for adjacency.

What the check refuses #

The claim that the cut changes nothing is easy to state and easy to get wrong, so it is checked twice rather than argued.

The cut has to actually split something. A seam that missed every region would make the comparison a comparison between a graph and itself. On the fourteen-region partition it splits six, and on every partition tried it splits between four and eight — enough that the identification is doing work.

And the two graphs are compared edge for edge, not by their colour counts. Two graphs can need the same number of colours and be entirely different graphs, so a check that compared only the chromatic numbers would pass on a coincidence. What is required here is that the contracted adjacency list equals the sphere’s, entry by entry, and it does on all five partitions.

That second check is the one that makes the finding a theorem exercised rather than a number observed. If a cut ever did add an edge, this is the check that would find it, and the fact that it never does is what licenses the general statement.

Why a colouring is the right instrument here #

A colouring is an odd thing to measure a projection with, and it is the right one for a reason worth stating.

Almost every quantity this collection computes is a metric one: a scale factor, an angle, an area, a distance. All of them change under a projection, which is the subject. A chromatic number changes under nothing at all — it is a property of the adjacency graph, and the adjacency graph is a topological invariant of the partition.

So a colouring is an instrument that should read the same before and after, and an instrument that should read the same is the only kind that can detect whether something was destroyed. If a cut had added an edge, the colouring would have moved; the fact that it does not is a measurement rather than a restatement.

That is the same logic what survives a change of coordinates applies to the principal scales, one level up: an invariant is useful precisely because a change that leaves everything else alone leaves it alone too, so any movement in it is information.

The converse is worth stating too. If an operation on a map does change the colouring, it has changed the adjacency, and a change in adjacency is a change in what the map claims about the ground — two regions are drawn as touching that do not touch, or the reverse. So the colouring is not merely an invariant that survives; it is a test that a rearrangement was faithful, and the exclave measurement above is the case where it correctly reports that one was not.

Where the model stops #

The partitions are Voronoi cells of stated sites, which are convex on the sphere and therefore simply connected. Real political regions are neither, and a region with a hole in it — an enclave entirely surrounded by one neighbour — is a different case again: it costs no extra colour at all, because it is adjacent only to its host.

The colouring is exact and the graphs are small. At thirty regions the backtracking search is instant; at a thousand it would not be, and the four-colour theorem’s own proof is famously a computation rather than an argument. Nothing here re-proves it; what is measured is that these particular graphs need four and that the cut does not change the graph.

And “adjacent” is defined by a shared boundary curve. Two regions meeting at a single point are not adjacent, which is the theorem’s own convention and which matters: four regions meeting at a point would need only two colours between the diagonal pairs, and a partition where three or more boundaries meet at a point is the case a grid-based adjacency test gets right by accident and a boundary-intersection test can get wrong.

The generalisation #

Cutting a surface changes its picture and not its combinatorics, provided the pieces are put back.

That sentence is what a topologist means by saying the cut sphere and the sphere are the same object with different presentations, and it has a practical form worth carrying: any property computed from adjacency — a colouring, a clustering, a shortest path through neighbours, a contiguity constraint in a redistricting problem — is unchanged by which projection the data was drawn in, and is broken by any pipeline that reads adjacency off the drawing.

The failure is not that the projection is wrong. It is that the drawing is a lossy presentation of a graph, and the loss is exactly at the seam, where every projection has to have one.

Who found it, and when #

The four-colour conjecture was made by Francis Guthrie in 1852 while colouring a map of the counties of England, and stood until Appel and Haken’s computer-assisted proof of 1976 — the first major theorem whose proof nobody could check by hand, and the reason the subject is as famous outside mathematics as inside it.

The exclave caveat is as old as the conjecture and was always stated with it: Guthrie’s problem is about connected countries, and every popular account mentions the exception without measuring it. The observation that a projection’s cut is not such an exception appears to be nobody’s, presumably because it is obvious to anybody who states the theorem carefully and invisible to everybody who does not.

The square-root law also says which partitions to worry about, and it is not the fine ones. A partition coarse enough for the seam to split half its regions is a partition of a dozen pieces — which is a diagram rather than a map, and is exactly the size at which a reader would notice a country coloured differently at the two edges of the sheet.

Where the ladder goes next #

Five rungs treat the removed set as a boundary — something the map gives up, works around or is cut along. What none of them asks is what the removed set does to a quantity that is integrated over the sphere rather than evaluated at a point, where a set of measure zero should contribute nothing and, on a projection, does not.