The Four Colour Theorem

February 28, 2009 at 12:03 am (Percy) (, , , , , , , , , , , , , )

The Four Colour Theorem is a famous problem in mathematics. It is very simple to express, but proved very difficult to solve. The method of solution was both new and controversial, to the point where some mathematicians still consider the question unanswered.

Early Formulation

In 1852, a graduate student by the name of Francis Guthrie noticed something interesting when he was colouring in a map of the English counties. He discovered that he could colour it all with only four colours, so that no two regions which were adjacent (that is, shared a common border) had the same colour:

As any good mathematician would do in this situation, he generalised the question – is this true of all maps? If some catastrophic occurrence befell the English counties and all the lines were redrawn, would he still only need four colours? What about a completely abstract partitioning of the plane, such as this:


Yep, still only four colours!

He simplified things down a little bit – countries that had more than one connected piece were disallowed, to avoid situations like these:


There is no way to colour this map with four colours, if both the regions marked A are to be the same colour.

It’s easy to show that at least four colours are needed (try it yourself!), but he couldn’t answer why only four were needed. No doubt he tried many different combinations, scribbling in notebooks and trying to find an easy counterexample. Instead, he passed the problem on to someone else.

Difficulties

Augustus De Morgan was a rather famous mathematician – anyone who has studied complex numbers will no doubt remember De Morgan’s Laws, not to mention his work on solidifying the method of proving by induction. He was able to prove a simpler result, which he hoped to generalise: any map with five (or fewer) regions could be coloured with only four colours. However, he couldn’t prove it for an arbitrary number of regions.

The problem was captivating enough, so it was passed around the mathematical community, attracting attention from brilliant minds such as Sir William Hamilton and Arthur Cayley.

After the problem was published in the journal Proceedings of the London Mathematical Society, a man by the name of Arthur Kempe struck upon a brilliant idea.

First he proved that any map has a region with five or fewer neighbours (which is quite remarkable, considering the generalities in which we’re talking). He described a process of shrinking which he claimed was reversible: if a region has three or fewer neighbours, we can shrink it away so that the map now has one less region to colour. We shrink everything down until our map only has four regions, colour those arbitrarily, and reverse the process:

shrink1
The grey regions are shrunk one at a time until we have only four regions – they are coloured, and the shrinking process is reversed.

Everyone was happy for 11 years, until Percy (!) Heawood found that the process wasn’t as reversible as everyone had assumed: a region with five neighbours couldn’t be shrunk like this (so that you could colour the rest and put it back nicely), and that was an unavoidable for some maps. The proof was sunk.

And yet, no-one could find any map that required more than four colours. They tried everything they could think of, but mathematicians are always (or should be) mindful that they are rather meagre minds in the light of the massive order and reason they are wrangling with – perhaps people just weren’t clever enough to come up with the required counterexample!

The language of graph theory was being developed, and was nicely adapted to this problem. Instead of considering countries and regions, the graph theorists considered coloured points, with lines between them representing adjacency:

With the results of graph theory now at their disposal, mathematicians quickly dispatched the Five Colour Theorem – I read the proof, and actually reproduced it rather faithfully in my exam, when I took Graph Theory in second year. However, the Five Colour Theorem wasn’t much help – moving from a graph that is five-coloured to one that is four-coloured often requires a lot of recolouring, as can be seen in this example:


A five coloured map.


The same map, now four coloured – note that the central blue region is now green, and its lower left neighbour is now blue.

In 1922 a man by the name of Philip Franklin proved that any map with 26 or fewer regions could be four-coloured. His proof used an idea called a reducible configuration, first introduced in Kempe’s proof (though not named as such). The idea was similar – take a number of adjacent regions, remove them, and four-colour the remainder. If you can put the regions back, regardless of how you four-coloured the remainder, then the regions are said to form a reducible configuration. Note that this is a generalisation – we are removing groups of regions, rather than one-at-a-time like Kempe proposed.

The idea was therefore formulated that would later be the starting point of the proof: prove that every possible map has a reducible configuration. Then, when you remove it from a particular map, the new (and simpler) map will also have a reducible configuration, and you can repeat the process and we have our result.

But what do these reducible configurations look like? It was demonstrated that a region that has four or fewer neighbours was reducible, but was that it? Could this turn into a proof?

A new age of proof

In 1970, Wolfgang Haken began his search for the full list of reducible configurations. Most estimates put the number at about 10,000, but the number might have been anything up to infinite (therefore frustrating his search for an exhaustive list). Working with another mathematician, Kenneth Appel, they developed computer software to help them find this list. They wrote their program, fired it up, and hoped that it would one day terminate and say “Here it is, the full list!”.

In just under 1,000 hours (about 6 weeks), the process stopped at 1,936 reducible configurations. They had found the list. Every map had at least one of these configurations – if you removed it to make a simpler map, the new map would contain one of these 1,936 configurations which you could take out. Eventually you could get down to just four regions, colour those and reverse the process. Thus the theorem was proved.

It was one of the first computer-assisted proofs to be presented, and as such gained a lot of attention due to the problem’s age – computers had achieved something humans were unable tackle with over a hundred years of pondering.

Scepticism and acceptance

Modern computers can do Haken and Appel’s computation in just under an hour, but the computation is so hard that no human could ever hope to do it, even if they devoted their entire life to this theorem. Mathematicians were very wary of this result – it comes down to trusting that the computer has done things the way you wanted it to. Computers are rather predictable machines, so most mathematicians do accept the proof today, but there are still some that remain sceptical.

Perhaps a bigger problem is that the proof doesn’t give us a very good understanding of what’s going on – what is it about a plane that it can be coloured in this way? So far, the only answer we have is that we’ve tested all the possible cases. Mathematicians want to be able to understand things like this, to assist in our generalisations.

If we are colouring a sphere or a cylinder, the result is the same. But what if we were to colour a torus, or donut shape? In that case, we actually need seven colours:


Seven regions, each with six neighbours, if we were to roll it together like so:


…so we know we need at least seven colours. Is seven all we need? Again, we’d need to feed all of this into a computer, which would probably give us an answer. The method of proof is therefore “give the computer a surface, and it will test it for you”, rather than a nice formula to describe how many colours you need, no matter how your object is sitting in space. What about a donut with two holes? What about a Mobius strip? The answer is the same – ask the computer.

What about higher dimensions? Again, ask a computer. We don’t have a good knowledge of what the connection is between the shape of an object and how we colour it – we just know that if we do a whole lot of calculations, a computer will give us an answer.

The fact that four colours is the maximum number of colours we need is now clear. However, the way that the fact was proven makes it almost useless to help us in our understanding of what’s really going on. The problem is therefore still being worked on to this day, so that one day humanity may be able to understand without the aid of a computer. We’re working towards a better answer, even though we already know what it is.

(I predict that computer assisted proofs play an increasingly prominent role in modern mathematics. As computer power begins to outstrip the capacity of the human brain, we will want to answer questions beyond our own power to solve. We won’t be able to help ourselves!)

Mathematics is often portrayed as a black-and-white, right-or-wrong subject. Whilst this may be true for much of high school mathematics, it is clearly not when it comes to problems like these. What it means to be right, how you’re right, how you go about finding answers and whether you can use your methods to answer bigger questions is far more important than simply knowing whether your attempts agree with the proverbial answers in the back of your textbook!

Advertisements

7 Comments

  1. naboolio said,

    That was a really interesting post. Thanks Andrew! 😀

  2. juliadactyl said,

    Man, you have the best maths ever. It’s all beautiful shapes and colours and awesome shit, and then you explain how it works and why it works and that is SO RAD.

    I also like a subject that goes “huh, wonder why this happens?” rather than just going “okay, I’ll need four colours.” “Here, I’ll need five.” I am beginning to understand why pure maths is so important – higher thought is a fairly fundamental aspect of being a human being, of explaining the world around you rather than just accepting it, because once you can explain it you can change it and that’s what humans do, so pure maths is like, essentially, one part of “thinking” which is hugely necessary for our survival and evolution as a species.

  3. Danoot said,

    aww yeah, graph theory. I need to: get my graph theory on.

  4. Heather said,

    Oh, rad. I remember a bit about this from my year 7 maths assignment, which had us researching a bunch of different mathsy things. It was pretty cool!

  5. capnsilver said,

    This totally blew my mind. It was pretty awesome.
    However it’s probably not a good thing that what I got out of it most was that the 5 colour diagragm was so much more aesthetically pleasing than the 4 colour.

    • juliadactyl said,

      I find I really need some purple and orange to keep it going. Rainbow spectrum FTW. The seven-colour one, however, makes me sad.

      Kind of like the brown colour in De Blob – there are some really gorgous, rich shades of brown, but they go with this sort of khaki-grey-beige monstrosity. It offended one’s sense of reason and aesthetics, is what it did.

      I remember being, like, 10 or something and looking at a map of the world in geography, and it was coloured like this. I remember getting really irritated that it was just sort of coloured so that the countries were different colours, and that those colours didn’t seem to make any sense. I much preferred the maps where there were gradients of colours depending on statistics, or where colour represented something like religion, or language, or something like that. I could see why the four colours were used, but honestly, it felt to me like it would be more okay to have a black and white map, than to make it look like countries belonged together for no reason than they didn’t have touching borders.

      It turns out that tiny Julia was just as anal about colour and meaning as grown-up Julia. It’s kind of cool learning about why there were four colours, though.

  6. chromefist said,

    It seems like a simple problem – is it just tantalisingly beyond our grasp, or are there whole areas that need to be filled in before we can figure out why? Or are we not really sure?

    If you could map mathematics, would this be a hole in the centre, a loose thread near the edge or somewhere off the table marked “Here be Dragons”?

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: