I understand that any two-dimensional map can be filled in using only four colors. But I can find out how to fill in this map with only four colors.
Can the title be changed to four color map.
There seem to be quite a few solutions. Here’s one, with a couple of variants:
http://img210.imageshack.us/img210/952/4colourmap6np.png
http://img210.imageshack.us/img210/4663/4colourmapv27an.png
http://img210.imageshack.us/img210/9514/4colourmapv39ga.png
I remember reading about the four-colour map theorem at school, and about how it had only recently been proven, with the aid of computers.
I thought (and still think) that it’s remarkable that there is no “simple” proof for this, as after doodling around for a while it seemed totally intuitive that four colours would be sufficient for any map - every time you bring two regions together, such that they cannot share a colour, you are by definition separating two other regions, so that they can share a colour.
It’s odd how something this simple cannot yield a straightforward proof - as I understand it, the proof was found by reducing all possible maps into a set of topologically distinct maps, or something like that.
Not so - Picture two regions as you suggest - perhaps a circle split into semicircles. Then two other regions are ‘C’ shaped - picture a larger circle around the first circle, cut so that it is also two regions.
Sorry, I didn’t make myself clear. I meant, “From the starting point of a map which requires four colours”.
The map you describe needs four colours (I am picturing a circle, divided in two by a horizontal line,and coloured, say, red on top and blue below, surrounded by another circle divided vertically into yellow and green, such that all segments touch each other).
The outer zone can now be, say, red. So now imagine we connect it to the inner red segment, by extending it between the yellow and green outer C-segments. Now it will have to be white. OK, so now connect it to the inner white segment in the same way – and of course you have now disconnected the yellow and green segments, so they can now be both coloured yellow and the outer segment can be green.
It’s very hard to put into words, it’s just kind of intuitive. Try it and you’ll (hopefully) see what I mean
Sorry, where I said “white” in that last post, I meant “blue”, of course… I’d forgotten what colours I was using!
And to clarify, on thinking about it a bit more, what I really mean is that every time you bring together two regions, each of which is currently forced to be the same colour, you are by definition breaking a connection elsewhere in the map, such that a different colour can now be used.
I told you it was hard to put into words, but I know what I mean 
I don’t believe that this is true. The four color theorem is generally expressed in terms of graphs, where you have a set of points (vertices) and set of line segments connecting pairs of them (edges). The theorem states that as long as no edges intersect each other, you can assign one color out of four to each vertex and be guaranteed that no two vertices with a common edge have the same color.
Here’s a counterexample to your idea: Imagine a graph with three vertices (1, 2 and 3) and edges between 1 and 2 and 2 and 3. Now add an edge between 1 and 3. Which pair was disconnected?
Cecil says, in this 1984 column, “recently” means 1976.
http://www.straightdope.com/classics/a1_126b.html
I don’t think that counts as a counterexample, because the original map/graph does not require four colours. Sure, you can connect two regions in a three-colourable map without breaking a connection.
What I said (eventually!) is that if you have a map that already requires four colours, you can’t connect two regions that currently require the same colour, without breaking another connection that is already there. You can see that this also works using the graph/vertex model.
Obviously this is true (since the theorem has been proved). What I meant is that it just seems throughly intuitive, albeit hard to express in words, so it’s surprising that the proof is so hard to find. Play around with some doodles on a bit of paper and you will see what I mean. Making a connection that would make the map require 5 colours ALWAYS breaks a connection elsewhere on the map. It just does But of course, being obviuous doesn’t mean that something is easy to prove mathematically.
“Recently” when I was at school in the 1980s, that is.
I think you’re misundestanding what the proof was. It’s trivial to show that four colors are needed for certain maps. What was so hard was to prove that no map existed where five colors was the necessary minimum.
This is a well studied problem in Computer Science and Graph Theory. Refer to these links at Wikipedia for more information. The second link goes over the Four Color Theorem and some counter-examples in terms of maps and such.
http://en.wikipedia.org/wiki/Graph_coloring
http://en.wikipedia.org/wiki/Four_color_theorem
No, I’m not misunderstanding it.
If you have a map that requires four colours, it seems obvious that if you extend two regions that are currently the same colour such that they touch one another (and would therefore require five colours), you will ALSO be breaking another connection, thus allowing the four-colourness to be restored.
E.g. see this map: http://en.wikipedia.org/wiki/Image:4ct-non-counterexample-2.png
Let’s say you create a common border between the topmost green circle segment and the green central circle, by extending a salient up from the central circle between the yellow and blue quarter-circles.
Now, clearly these sections cannot both be green, as they are touching. But in connecting them, you have destroyed a connection between the yellow and blue quarter circles, so these can now be the same colour. Let’s make them both yellow; now all that you need to do is swap the right-most outer-ring segment from yellow to blue, and the four-colourness is preserved.
Sorry, I really should have read that through a bit better, I neglected to explain the last steps…
The top two inner segments, which are now separated, can now be yellow, the bottom tow inner segments remain blue and purple respectively as before, and now the outer rings, from top and proceeding clockwise, go purple, green, yellow, green.
The inner remains green and the background outer region remains blue, as before.
These problems are very difficult to describe verbally, but surely you can see what I mean when I say that every new connection between like-coloured regions in a 4-colour map results in a breaking of another connection?
Sorry, I got called away and I should have hit preview instead of submit.
What I should have continued to say is that the mathematical proof of the sufficiency of four colors cannot be given by doodling connections on a piece of paper. Mathematical maps are far more complex than a series of areas. Colophon’s naive explanation fails because it cannot account for the cascade of color changes that are made possible by any new connection or area. The mathematical proof must account for cases of near-infinite complexity that cannot be approximated by drawing a circle and coloring in the interior. This is in fact precisely why all earlier attempts, including those by people who spent years drawing ever-more complex partitions, failed. Blaster Master’s four color theorem link has an example of exactly why this is the wrong approach.
Incidentally, IIRC it’s only really difficult on genus-zero surfaces. For higher genera the analogous theorem is easier to prove.
(full disclosure, in case I’m wrong: I am not as much of a graph theorist as maybe I should be)
IMHO, it should be renamed the four-color postulation.
Based on…?