At 02:55 AM 12/25/03 -0800, you wrote:
In the case of the US, the completely reduced map is empty. This is also true for the maps of Europe and Asia, Africa, South America, and the departments of France. It is easy to construct a map in which every country has four or more neighbors. Indeed, as Kempe proved, there are maps in which every country has five or more neighbors.
My intuition is that smallish not-completely-reducible maps are rare in some sense, though in all the senses I can think of the probability of complete reducibility declines, eventually to zero, for maps with enough regions. Computer experiment would probably be instructive. Proposed experiment 1: Voronoi maps Sprinkle N points randomly on a rectangular continent. Construct the map in which each chosen point is the capital of a region; each point belongs to the region with the nearest capital. Check to see if the resulting map is completely reducible. Repeat many times and collect statistics on the prevalence of complete reducibility for different values of N. Proposed experiment 2: Census of reducibility of planar graphs Enumerate all connected planar graphs on N vertices and record whether each is completely reducible. Construct a table, being careful to keep Neil Sloane in the loop, because new sequences are bound to arise. Different criteria for when two graphs are different might alter the statistics and produce different sequences. -A