Four Pens, One City: Colouring Leicester's Ring Road Without a Clash
Grab a tube of felt tips and a rough sketch of the city. We are going to colour in Leicester — but with a rule that turns a doodle into a genuine piece of mathematics.
The rule that changes everything
Here it is, and it is the only one: two areas that share a border must get different colours. Areas that touch only at a single point are allowed to match. That little clause matters more than it looks, and we will come back to it.
Most people, handed a map and four colours, can make a decent fist of it. The interesting question isn't whether it can be done — it's why four is the magic number, and where a real city makes life awkward.
From street map to network
A map is a picture, and pictures are hard to reason about. So swap it for a network. Each district becomes a dot. If two districts share a boundary of any length, join their dots with a line. What you now hold is a graph, and colouring a map is exactly the same job as colouring the dots so that no line links two dots of the same colour.
The conversion is worth doing once by hand. Sketch the districts, write a letter in each, then list the pairs that touch. That list — the adjacency list — is the whole puzzle, stripped of geography. Charts, registers and timetables can all be built from it later.
One warning from the real world: water is not a district. The Soar winding through Abbey Park, the Grand Union Canal near Aylestone, the brooks running under the ring road — treat them as walls, not regions. Two banks on opposite sides of a river are not adjacent unless there is dry land connecting them somewhere else along the boundary.
What Leicester looks like from above
Ignore the detail and the shape that emerges is strikingly simple. Inside the ring road sits the city centre. Around it, like segments of an orange, sit five broad districts:
- Abbey and Beaumont Leys to the north
- Belgrave and Rushey Mead to the north-east
- Highfields and Stoneygate to the east and south-east
- Aylestone and Knighton to the south
- Braunstone and the Fosse corridors to the west
Each district shares a boundary with its two neighbours, so the five of them form a closed ring. And the centre, hemmed in by the ring road, touches every one of them.
That structure — a hub with an odd number of spokes around it — is where the fun starts.
Four colours: a very short history
The question was first raised in 1852 by Francis Guthrie, who noticed it while colouring a map of English counties. Augustus De Morgan passed it around; for over a century it stayed stubbornly unsolved. Alfred Kempe published a proof in 1879 that survived eleven years before a flaw was found. Percy Heawood salvaged the five-colour version, and five colours were the best anyone could guarantee for decades.
Then in 1976 Kenneth Appel and Wolfgang Haken proved that four really is always enough — using a computer to check nearly two thousand unavoidable configurations. It was one of the first major theorems proved with machine assistance, and it caused a proper row about what counts as a proof. A simpler version followed in 1996, and in 2005 Georges Gonthier formalised the whole thing in the Coq proof assistant. Four colours, no asterisks.
Why three pens will not do
Here is the argument, and you can run it in a classroom in five minutes.
Imagine five districts arranged in a ring, each touching the two beside it. Colour them in turn. One takes blue. Its neighbour cannot be blue, so green. The third cannot be green, so blue again. Keep going and the alternation works beautifully — until you close the loop. The fifth district borders the fourth and the first, which have ended up in different colours, so it needs a third colour. An odd ring always demands three.
Now drop the city centre into the middle. It touches all five. Whatever three colours the ring has used, the centre must avoid every one of them, so a fourth pen comes out.
That is a proof, not a hunch: our simplified Leicester needs four colours, and no cleverness with the shading will get it down to three. Push the ring up to four districts, or six, and the alternation closes neatly — three colours would then be plenty.
The challenge
Draw a circle for the city centre and five wedge-shaped districts around it, each touching its two neighbours, all five touching the centre. Label the districts A to E going clockwise, and the centre C.
- Write out the adjacency list as pairs of letters.
- Colour it with four colours, obeying the border rule.
- Now try to do it with three. Give yourself five minutes, then write down the reason it cannot work.
- Add a sixth district between any two existing ones so the ring becomes even. Recolour. How many pens do you need now?
Good extension for a rainy lunchtime: colour the actual ward map of Leicester. There are twenty-one wards, and the map on the council website is a genuine planar map. Count how many colours a simple greedy approach uses — take the wards in any order, give each the lowest-numbered colour not used by a neighbour — then see whether a smarter order beats it.
Where this turns up in real life
The same graph-colouring idea decides which radio frequencies mobile masts may share without interference, how exam boards pack timetables without clashes, and how a Leicester school fits its options blocks into a week. Every one of those is a colouring problem wearing a different coat.
So next time you are stuck at Red Hill Circle, look at the signposts for the districts around you. Five neighbours, one centre, four pens. The city has been hiding a theorem in its street plan all along.
