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.
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).
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 
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?
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.
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.
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.