Countries
Borders
Colours used
Clashes

More about the four colour theorem

Four colour theorem map painter

However complicated a map is, four colours are always enough to colour it so that countries sharing a border never share a colour. The statement is simple enough for a child to test with crayons, yet it took more than a century and a computer to prove. Paint a random map yourself, see which borders clash, and then watch three methods do it, from a quick greedy rule that sometimes needs a fifth colour to a backtracking search that always manages with four. Pick a colour and click countries to paint them; a border turns red when two neighbours share a colour. Countries that only touch at a corner may share one. Or let the computer do it: choose a method and press Solve to watch it, or Step to follow one move at a time. Fewest colours checks whether this map could do with three, or even two. New map draws another map, and Show the neighbours draws the network of countries that share a border.

How it works

  1. Choose the number of countries and press New map, or start with the map shown.
  2. Pick a colour and click countries to paint them, watching for red borders where neighbours clash.
  3. Choose a method and press Solve or Step to watch it colour the map, and press Fewest colours to see how many this map needs.

From maps to graphs

Put a dot in every country and join two dots when their countries share a border. The map becomes a graph, and colouring the map is the same as colouring the dots so that joined dots differ. Because maps are drawn on a flat sheet, these graphs are planar: they can be drawn without crossing lines. Countries meeting at a single point, like four squares at a corner, are not neighbours. The four colour theorem says that every planar graph can be coloured with four colours. Switch on Show the neighbours to see the graph of the current map.

Three ways to colour

Greedy colouring takes the countries one at a time, those with most neighbours first, and gives each the first colour its neighbours have not used. It is fast but short-sighted, and on some maps it reaches for a fifth or even sixth colour. DSATUR, invented by Daniel Brélaz in 1979, always picks next the country whose neighbours already show the most different colours, which usually avoids that trap. Backtracking tries colours in turn and, when a country has none left, undoes its most recent choices and tries again; it always finds a colouring with four colours, sometimes after going back many times.

Frequently asked questions

Why are four colours always enough?

Nobody has found a short reason. The proof by Kenneth Appel and Wolfgang Haken in 1976 showed that every map must contain one of 1,936 small configurations, and that each of these can be removed and the colouring later restored; checking all of them took more than a thousand hours of computer time. A simpler computer proof by Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas in 1996 needs 633 configurations, and in 2005 Georges Gonthier verified a proof completely with the Coq proof assistant.

Do some maps need all four colours?

Yes. Four countries that each touch the other three, like a country surrounded by three others in a ring, need four. Many maps, though, manage with three, and Fewest colours finds out for the map on the screen. Deciding in general whether a map can be coloured with three colours is a hard problem, NP-complete, even though four colours always suffice.

Why does the greedy method sometimes use five colours?

It colours each country once and never changes its mind. An early choice can leave a later country surrounded by all four colours, and the only way out is a fifth. Backtracking would instead go back and change the earlier choices.

Is the theorem true on other surfaces?

On a sphere, yes: it is the same as the plane. On a torus, the surface of a doughnut, some maps need seven colours, and seven are always enough, as Percy Heawood showed. If countries may consist of several separate pieces, like a nation with colonies, four colours are no longer enough.

Is anything sent to a server?

No. The map, the colouring methods and the check run in your browser. Your settings stay in this browser's local storage.

Ready to try it?

Open PictorX in your browser — no install, no credit card required to start.

Go to Editor