A couple of days ago I was discussing the four-colour theorem with one of my mathematics students, and I realized that there is some misunderstanding of it even among bright young (amateur) mathematicians. (Not to imply that even older or professional mathematicians don't sometimes misunderstand it as well)

And so I thought I would take this opportunity to give a brief review of some of the overlooked details...

Suppose you take a two-dimensional map (by which I mean a bunch of lines separating different regions, written on some two-dimensional surface) and try to colour it so that each region has a different colour than all of its neighbours. How many colours do you require?

Anyone who says four has already fallen into a common misconception.

On a flat plane or on a sphere, it has been (almost?) proven that you can colour any map with four colours. But if you draw a 2D map on the surface of a torus then you can easily make maps requiring seven colours! And with more complicated maps you can require any number of colours. However for the rest of this article, I will stay with a planar map and four colours.

Now I hear some readers questioning the phrase 'almost proven'. The four-colour theorem was proven over thirty years ago, so where is the dispute. The concern that has been raised by some is that this is a very simple problem to state, and should have a simple proof. The only known proof though required a powerful computer to first calculate all possible types of map, and then the computer tries to colour them all with four colours. The computer confirmed that it was possible, and in truth other mathematicians have since repeated it with the same result, so there is hardly any doubt that it is true. But at its heart, mathematics should have logical proofs that anyone can read, rather than a computer print-out that says the theorem is true.

 The next misconception that must be addressed is the requirements of a proof of the four-colour theorem. Inevitably whenever I or another writes about it, there comes a flood of 'proofs' from amateur mathematicians who have misunderstood the theorem and only prove one part (always the simple half of the proof).

The first part of any proof of the four colour theorem requires proving that it is impossible to have five regions all sharing boundaries with each of the other four. There are many ways to do this, but my favorite is to start with a dual-map which is formed by placing a vertex in each region, and then connecting the vertices of neighbouring regions with an edge. Then it is very simple to prove using Euler's famous equation that 

2 = F - E + V = 2/3 E - E + V = N - 1/6 N(N-1) = 1/6 N(7-N)


 where N is the number of colours and where we assume that every vertex is connected once to every other vertex (so that E = N(N-1)/2 ). This equation is true only for N = 4, so the best that we can do is have four regions sharing common boundaries, which proves also that at least four colours are needed.

 What hasn't been proven in a simple way is that you cannot have very large maps where a fifth colour is required. This can be demonstrated using a ring of regions:



In this map, only three regions ever share common boundaries, and in fact for any subset of that ring you can colour the entire map with three colours. So this could be a three-coloured map. Except that when the entire ring is considered, you always find the final region in the ring requires a fourth colour.



The unanswered question then is are there any similar rings or more complicated chains of regions in a map that requires a fifth colour? The computers tell us the answer is no, but no one has been able to prove it by hand. It is an interesting challenge.