It turns out that there is even more to say on the communes of Lichtenstein.

First of all, there is a 5-clique in the communal graph, as Brian Hayes pointed out. But there are two different excluded subgraphs for planarity – so if we aren’t looking specifically for the chromatic number, but rather how this graph fails to be a “normal” land map, we might want to see whether it realizes BOTH.

It turns out that it does.

The following are two highlighted versions of the Liechtenstein communal graph.

The embedded K5 with edges in blue.

The embedded K33 with blue and red vertices.

I reached to the same conclusion without searching the clique of size 5 and K_3,3. Uses only spiral chain coloring algorithm on the map and uses the same color for the common communes.

See:

http://www.flickr.com/photos/49058045@N00/2985004680/

Cahit