How many colours does it take to colour the map of Romania?

The map without the map#

To answer the question, you can forget the shapes of the counties. All that matters is who borders whom. Put a dot in each of the 41 counties and in Bucharest, and draw a line for each shared border: 42 dots and 102 lines. Brașov has the most, eight.

A short border counts as much as a long one: Buzău and Brașov touch along 2.3 km, Vaslui and Vrancea along 3.5 km, and they still may not share a colour. A single shared point does not count at all. Two countries that meet only at a corner may share a colour. Otherwise a pie cut into many slices, all meeting in the middle, would need a colour for every slice.

The dot drawing has a property shared by every map whose countries are each in one piece: its lines can be drawn without crossing. Mathematicians call it a planar graph. That turns the question into one about every map whose countries are each in one piece: are four colours enough for every planar graph?

Show me only the dots

124 years from the question to the proof#

1. 1852

   Francis Guthrie, colouring a map of England, guesses that four colours are enough for any map. His brother Frederick takes the question to their teacher, Augustus De Morgan. On 23 October, De Morgan writes to William Rowan Hamilton. Hamilton replies that he is not likely to attempt the “quaternion” of colours very soon.

2. 1878

   Arthur Cayley asks the London Mathematical Society whether the problem has been solved. The next year, the barrister Alfred Kempe publishes a proof.

3. 1890

   Percy Heawood finds the error in Kempe's proof, eleven years after it appeared. What survives is enough to prove that five colours always suffice.

4. 1976

   Kenneth Appel and Wolfgang Haken, at the University of Illinois, cut the problem down to about fifteen hundred configurations and have a computer check them. Part of the proof is the computer’s work and cannot be checked by hand.

5. 1997

   Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas publish a simpler proof: 633 configurations and 32 rules. It still needs a computer.

6. 2005

   Georges Gonthier and Benjamin Werner have the proof checker Coq verify every step, including the part that had been left to programs written for the proof.

Does your commune have an odd ring?#

Below the 41 counties and Bucharest lie 3,181 communes, towns and cities (Bucharest counts as one here), with 9,251 borders between them. In Romania a commune (comună) is a rural municipality of several villages, the smallest unit with its own town hall. The odd ring, which appears ten times among the counties (around Mureș, Bacău, Ilfov and seven others), appears here at 1,537 places, almost half. Each of them, alone with its neighbours, already needs four colours.

Where the theorem falls silent#

The four colour theorem has a condition that school usually skips: every country must be in one piece. In the official ANCPI boundaries of the units, 39 communes, towns and cities are not. One well-known case is Păltiniș, a mountain resort that belongs to the city of Sibiu but is cut off from it by other communes. Next to it, Cristian and Poplaca each come in three pieces, and Săliște in two.

Here is what follows. Sibiu, Cristian and Gura Râului each share a border with Rășinari, with Poplaca and with Orlat. Only Sibiu reaches Orlat the long way, through Șura Mică and Săliște. The shortest of these borders is 4.6 km long, so this is no drawing error. It is the old puzzle of three houses and three wells: join every house to every well without two paths crossing. Try it below.

In 1930 Kazimierz Kuratowski showed that a drawing of dots and lines can fail to be flat for only two reasons, and this one, three houses and three wells, is one of them. On the map it works because four of them, Sibiu, Cristian, Poplaca and Săliște, are in several places at once.

Percy Heawood had thought of this as early as 1890: if each country may have two pieces, some maps need twelve colours, and twelve are always enough. Of the 39 places in pieces, any one of 24, joined up on its own, is enough to stop the commune drawing being flat.

Four are enough, all the same#

For Romania's communes the theorem guarantees nothing. All that is left is to try. Press the button and your computer or phone will search, in front of you, for a four-colouring of all 3,181 places. It starts from a hasty colouring, place by place, that leaves some neighbours alike. Then, step by step, it recolours a place that has a neighbour of the same colour. When it gets stuck, it starts again.

Three are not enough here either: any of the 1,537 odd rings shows it. So the answer for Romania, from the counties down to the last commune, is the same: four. For the communes, it came from a search, not from the theorem.

Colour in your county#

Pick a county and print it. You will need four pencils: not one of the 41 counties can be done with three, not even on its own. Bucharest, counted here as a single unit, needs only one pencil.