On Thu, 25 Dec 2003, John McCarthy wrote:
However, I haven't been able to find a map on the face of the earth in which every country has four or more neighbors.
If you're willing to color the ocean on your map also, then South America provides an example. In fact, it provides the minimal possible (planar) one, equivalent to the adjacency of the faces of a cube. Bolivia is surrounded by a ring of four neighbors, Peru-Chile-Argentina-Brazil and back to Peru, in which each touches the two around it. And every one of those neighbors touches the ocean. Bolivia has a fifth neighbor, Paraguay, which is postponable, but fortunately doesn't get in the way of Argentina and Brazil bordering each other. And better yet, these four contries each touch the other three, so the same region of the world also contains a minimal instance showing that four colors are necessary.
I'd be disappointed if the result was achieved with the aid of a disconnected country.
(As far as I know, there are four K_4's in the globe -- the above, another straightforward one in each of Europe and Africa, and one tricky one which does indeed use a disconnected country.)
I see no reason why our ancestors should have arranged their countries, states, provinces, and counties in such an easy to color way.
The things you're trying to color are small enough that you're coloring a map on the plane (and not, say, making use of the fact that it's on a sphere). A finite map in the plane where each region touches at least four neighbors seems to force relatively large regions around the outside boundary, compared to the inner regions -- another version of the cube, for example, looks like (bad ascii-art ahead): EEE DDDEEEE DDDaaEEE DDDaaccEE DDDbbccFF DDDbbFFF DDDFFFF FFF With nearby regions close to the same size, it's hard to deal with outside corners. (Which is why I thought using the ocean could help.) --Michael Kleber kleber@brandeis.edu PS:
Indeed, as Kempe proved, there are maps in which every country has five or more neighbors.
The dodecahedron is older than Kempe...