[QUOTE=ultrafilter]
No. The theorem holds for any map drawn on a plane.
[/QUOTE]
But he is putting an extra constraint on the problem - that two arbitrary regions be the same color. I’m sure that four colors would not be sufficient in this case - all you’d need to do to find a counterexample is find a coloring where region A is Red, and an arbitrary non-connected region B is constrained to be not-Red, then require B to be Red. We can call this Four Color Conjecture Prime, and it is not true.
My mistake, I misread the question.
[QUOTE=Colophon]
The reasoning doesn’t work because you can go from a 3-colour to a 4-colour map without breaking a connection.
E.g. if you have a red square touching a blue square, both inside a green circle: http://i4.tinypic.com/1040z7r.gif
you can simply add another square inside the circle, touching both the first two squares, and it has to be a fourth colour, say yellow: http://i4.tinypic.com/1040zlf.gif
But now you cannot introduce another region that touches all three of those those squares without breaking a connection between at least one of them and the outer circle. It’s just geometrically impossible - in order to form a continuous pathway from one to the other, it cuts off another section.
Let’s try: http://i4.tinypic.com/10411jk.gif That’s no good - it has separated the blue square from the green circle, so now the blue square can be coloured green. And if we take the left hand edge of the new purple region a bit to the right, allowing the blue square to be in contact with the green circle, we have now broken contact with the red square, so the new region could be coloured red. And so it goes…
OK, so what if we take the pathway outside, and not directly in contact with the other square the whole way round? http://i4.tinypic.com/104120z.gif
The new region is touching all three squares, and the green circle. But again, the blue square is cut off from the outer green circle, so there is nothing stopping it from being coloured green, once the “new” mini sections are recoloured appropriately: http://i4.tinypic.com/10412j5.gif And there we are back to our four colours again.
Or we could have the new section touching all three squares by cutting across the middle of them: http://i4.tinypic.com/10414c4.gif
But you still can’t avoid breaking connections - now the main area of the blue square is cut off from the main area of red square, so they can be coloured the same, and the small corner of red is cut off from the yellow, and the small corner of blue is cut off from the green. Again 4-colour is restored: http://i4.tinypic.com/10414sh.gif
Or you could go right outside the circle: http://i4.tinypic.com/10415c3.gif
But that doesn’t help either because you are ALWAYS breaking connections elsewhere in the map: http://i4.tinypic.com/10415pz.gif
All of which is pointless of course, but I find it interesting…
[/QUOTE]
What you’re arguing here is that K[sub]5[/sub] (the graph with five vertices and a edge between every pair) is non-planar and therefore not four-colorable. That’s a very old result, and the fact that it’s not four-colorable is immediately obvious.
In fact, if there’s no constraint that a “country” be contiguous, then no number of colors will suffice. Suppose that you have N countries, and that each country has a small, embassy-like enclave within each of the other countries. In this case, each country borders every other, so no two countries can have the same color.
There are, of course, various other restrictions that you can place that give you an interesting problem again. For instance, you might require that each country have no more than two contiguous pieces: I think (though I’m not certain) that in this case, 8 colors are required. You might also, as Martin Gardner once discussed, require that one of those pieces for each country be on the Earth, and another on the Moon (as I recall, in this case only 7 are needed).
[QUOTE=ultrafilter]
What you’re arguing here is that K[sub]5[/sub] (the graph with five vertices and a edge between every pair) is non-planar and therefore not four-colorable. That’s a very old result, and the fact that it’s not four-colorable is immediately obvious.
[/QUOTE]
Well, he’s also arguing that the only way to arrive at a non four-colorable map is to have a graph with five vertices and an edge between every pair. If that’s easily proven true, then the four-color map theorem is proved much more simply than it has been previously.
K(3, 3) is not four colourable and does not contain K5.
Oops! Yes it can 
[QUOTE=bup]
Well, he’s also arguing that the only way to arrive at a non four-colorable map is to have a graph with five vertices and an edge between every pair. If that’s easily proven true, then the four-color map theorem is proved much more simply than it has been previously.
[/QUOTE]
On a surface of genus 0 (a plane, a sphere, or anything that has no holes in the middle), a graph is planar iff it contains no subgraph which is topologically equivalent to K[sub]5[/sub] or K[sub]3, 3[/sub]. I don’t think that’s all that complicated a proof, but it doesn’t help one whit with the proof that every planar graph is four-colorable–the shortest known proof is still the 600+ cases that’s under discussion here.
I may be reading this wrong, but the heart of this argument seems to be that because it is geometrically impossible for five countries to all touch each other, there is never a need for five colors on a map.
I also initially had this rather naive idea; Robin Wilson’s *Four Colours Suffice * helped me understand why this idea is false, and it’s a book I highly recommend even for amateur (and, perhaps, professional) mathematicians.
It is possible to draw a map which requires three colors even though no three countries all touch each other. Imagine a pie (with infinite radius) cut into five slices; each slice is bordered by only two others, and there are no three countries which all border each other. However it is impossible to shade these five countries with only two colors; at least three are required.
Now if this pie is completely surrounded by a sixth “perimeter” country, we have the case that there are no four countries which all border each other (the perimeter country does border every other nation in the map, but the interior countries only border three others, and two of these bordermates are separated, so there are no four countries which all border each other). Yet this map requires four colors to shade it; the guarantee that no four countries all touch each other did not prevent the need for four colors on this map.
Here then are two examples of maps which require more colors to shade them than the highest “cluster” of co-touching countries in the map. Sure it’s true that no planar map can have a 5-country “cluster” of nations that all border each other. But the examples above prove this is insufficient to guarantee all maps can then be colored with four colors.
So?
[QUOTE=Mathochist]
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)
[/QUOTE]
You are right. On the surface of a torus, for example, seven colors suffice and that is not hard to prove. The same kind of argument on a sphere (or plane) shows relatively easily that five colors suffice. The problem is proving that five colors are never necessary.
I have had some of the proof explained. The first thing to do is assume that there is a map that requires five and choose one that with the property that if you delete any one area or merge and two adjacent areas, four colors suffice. Such a map is called a minimal criminal. So the problem is reduced to showing that no minimal criminal exists. You then show that there can be in the minimal criminal no region with only three or four neighbors. If there were, you could merge such a region with a neighbor, color the resulting map (this is where the minimality comes in) and then go back and color the original map. There is a little trick involved there that uses a version of the Jordan curve theorem. Then you show that there is always at least one region (actually always at least 12) that has only five neighbors. A little trick involving Euler’s F - E + V formula. The next step (here is where I lose the thread) is that if there are either two adjacent 5-regions (that is having five neighbors) or a 5-region adjacent to a 6-region. The case of two adjacent 5-regions is trivial, but the 5-6 case is not. But among the 5-6’s there is either a … or a … and the first one is easy. Well, the process converges and in 1976 they got it down to something under 2000 candidates for being a minimal criminal (this part was done by hand) and used the computer to eliminate each of them by hand. At the time, they used 1200 hours on the Illiac IV, a supercomputer of its day. In 1994, I met a mathematician who told me he had reduced it to some 500 or so minimal criminals and could do eliminate them on his home PC in one night.
The original solvers, Wolfgang Haken and Kenneth Appell, were a topologist and a computer expert and their knowledge merged well. About ten years earler I heard Haken talk about a man named Heesch who had been working for 30 years trying to do all this by hand and Haken was worried that Heesch would die and all his work and methods would be lost. Evidently, in the interim, Haken had undertaken to learn about Heesch’s methods and, with Appell’s help, bring them to fruition.
[QUOTE=Voyager]
But he is putting an extra constraint on the problem - that two arbitrary regions be the same color. I’m sure that four colors would not be sufficient in this case - all you’d need to do to find a counterexample is find a coloring where region A is Red, and an arbitrary non-connected region B is constrained to be not-Red, then require B to be Red. We can call this Four Color Conjecture Prime, and it is not true.
[/QUOTE]
Actually, you can make it sharper.
Say that a given country is spread into k pieces. Now dig a tunnel from one piece into each of the other pieces, and paint the walls of the tunnel the same color as the country. The country is now connected (where it was disconnected before) at the cost of raising the genus of the surface by k-1. So if you have n disconnected countries on a sphere split into a total of k pieces between them, the problem is equivalent to normally coloring a map on the surface of genus k-n.
In fact, we get the same result if we throw in all the other countries, since they need to change the genus by 1-1=0. So, coloring a map with n countries divided into k pieces total is the same as coloring a map on the k-n-holed torus.
[QUOTE=Happy Clam]
Supplementary question: In real-world maps (ie. ones that actually depict a variety of countries in relation to each other, rather than theoretical shapes), would it be possible to have a set of mixed-up countries that violated the four-colour theorem? I’m thinking of something like Germany 1918-1939, which was split roughly in half by the “Polish corridor”, which meant that you has a chunk of Germany (which needs to be the same colour as the rest of Germany) of in the middle of Poland. Could you therefore design a set of countries where the four-colour theorem would no longer hold?
[/QUOTE]
The Polish Corridor just separated East Prussia from the main part of Germany. Since Poland was already adjacent to Gemany, this didn’t add the need for any more colors to the map.
However, before unification, Germany was divided into many small princedoms which frequently had enclaves and enclaves within enclaves among each other. I’ve never seen a detailed map of Germany of this era, so I don’t know how many colors it would have taken to map it, but I would guess that five is too few.
Currently, I’m fairly sure you can map all countries with only four colors, provided you allow overseas territories to be mapped a different color than the home country.[sup]1[/sup] If this is not allowed, you need at least five colors.
[sup]1[/sup]Also ignoring claims in Antarctica, some of which overlap.
For the record, four colors only suffice in theoretical field coloring, not actual cartography. Most real maps I’ve seen use five or six colors (sometimes more) in addition to blue (or whatever) for water.
