Four colors suffice for any planar map: We’ve known that since 1977. If a map is divided into countries or provinces or other regions, and you want to color the map so that no two adjacent regions have the same color, you’ll never need more than four crayons. But there are a couple of definitions that have to be accepted if this theorem is to hold. First, “adjacent” means that two regions share a boundary segment, not merely a point or a discontinuous set of points. Second, a “region” has to be a connected area, so that you can reach any point in the interior from any other such point without crossing a boundary.
A few days ago the strange and wonderful Strange Maps blog called attention to this map of the Principality of Liechtenstein:
(The map comes from the Wikimedia Commons Atlas of Liechtenstein, which has a larger image.)
It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south). All the rest of the communes have enclaves and/or exclaves. (I confess that I didn’t know the distinction between these words until yesterday. They make a nice pair.) The most fragmented commune is Vaduz, which includes the principality’s capital. Vaduz consists of six isolated pieces; the smallest is a sliver about a kilometer northeast of the town of Planken.
In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?