I read that the four-colour map problem has only been solved by massive trial and error. That can't be right! I think the problem can be rewritten as "can you create a map so five countries all touch?" If this can't be done then there is no way of 'forcing' in a fifth colour and there should always be a way to only use four colours. Now, it is possible to prove that you can never have five countries all touching. Treat the countries as vertices. Treat the points of contact of borders as lines between the dots. By allowing the lines and positions of dots to distort freely, I find that all the possibilities are just rearrangements of the following system, which precludes the possibility of the fifth 'country' being connected to all the other four. There will always be one country which is encapsulated from the fifth country by three of the others, thus:

/--------------\
|..................|
|..................|
|..................|
0--------0----0
|\......../|.....|
|.\....../.|.....|
|..\..../..|.....|
|...\../...|.....|
|....0.....|.....|
.\...|..../......|
..\..|.../.......|
...\.|../........|
....\|./.........|
.....0---------/

Note: I have used full stops just to fill gaps. The email program deletes multiple spaces and tabs when I try to post. Annoying or what?

Unfortunately, the problem is more difficult. What you've proved is that you cannot have 5 countries each touching one another, but this isn't enough because the way you colour one bit of the map affects the way you colour another bit of the map. For example, suppose you have maps as below:



In diagram 1, suppose you have coloured A red, and B, C and D green, blue and yellow. To extend this colouring to include country E you would have to use a 5th colour, even though 4 colours would do (because you could colour B and D the same colour. This shows that the choices you make in colouring one area affect the possibilities elsewhere in the map. So the obvious way of colouring a map won't always work (starting with a country and just colouring the surrounding countries using colours unused).

Another way of thinking about it is diagram 2. In this picture, although you never got more than 3 countries all touching one another you still need 4 colours to colour the map. If your argument above worked for 4 colours (you cannot find 5 countries all touching so 4 colours always suffices) then it would work for this as well, there are no 4 countries all touching so you should be able to find a way to colour it using only 3 colours.

This is a good illustration of the difference between a global and local problem. A local problem is one which you can solve locally quite easily (such as the proof you gave showing that you cannot find five countries all touching) but it doesn't extend to work for the whole problem. In general, global problems are more difficult than local ones.

I included the graphs of each of the diagrams in the picture as well, because what you have proved is that given a drawn map, you cannot find a pentagon in the graph of a map with all the edges between vertices coloured in. However, you can find a square with all the edges coloured in (e.g. ABCE in diagram 1). Although there are only triangles in the graph of diagram 2, you still need 4 colours. This graph picture might be a more helpful one to understand why your argument doesn't extend to work for all maps. Hope that helps.

By the way, the mistake you made is a very common one even among mathematicians, in fact it is the most common wrong proof of the 4 colour theorem. A friend of mine who was in the final year of his degree in maths (and so should have known better) once told me he'd found a proof of the 4 colour theorem and it turned out to be this! :-)

Thanks for the compliment but, with diagram 2, doesn't this work:
A= yellow
B= red
C= green
D= yellow
E= green

I get the point generally. I'm still sure that there is always an appropriate way of arranging colours, but I can see that this needs proving. And when I've proved it I'll win a Nobel! (Fat chance...)

You're right, for diagram 2 I should have connected A to D (which still doesn't introduce any 4 countries all touching).

Good luck with the proof, if you find a short one you probably will win a Fields medal (the mathematical equivalent of a Nobel).