Following the featuring of the internal political structure of Lichtenstein on the Strange Maps blog, Brian Hayes asks for the chromatic number of Lichtenstein.

*Rahul pointed out that I made errors in transferring the map to a graph. Specifically, I missed the borders Schellenberg-Eschen and Vaduz-Triesen. The post below changes accordingly.*

Warning: This post DOES contain spoilers to Brian’s question. If you do want to investigate it yourself, you’ll need to stop reading now. Apologies to those on my planet feeds.

As a first step, we need to build a graph out of it. I labeled each region in turn with the exclaves numbered higher than the “main” region of each organizational unit. And then I build a .dot file to capture them all:

graph Lichtenstein { Ruggell -- Schellenberg Ruggell -- Gamprin1 Schellenberg -- Mauren Schellenberg -- Eschen1 Mauren -- Eschen1 Gamprin1 -- Eschen2 Gamprin1 -- Vaduz2 Gamprin1 -- Schaan1 Gamprin1 -- Planken3 Gamprin1 -- Eschen1 Eschen1 -- Gamprin2 Eschen1 -- Planken1 Eschen2 -- Schaan1 Vaduz3 -- Schaan1 Vaduz2 -- Schaan1 Planken3 -- Schaan1 Planken2 -- Schaan1 Schaan1 -- Planken1 Schaan1 -- Planken4 Schaan1 -- Vaduz1 Gamprin2 -- Eschen3 Eschen3 -- Vaduz4 Eschen3 -- Schaan2 Vaduz4 -- Schaan2 Vaduz4 -- Planken1 Schaan2 -- Planken1 Planken1 -- Schaan3 Vaduz1 -- Triesenberg1 Vaduz1 -- Triesen Planken4 -- Triesenberg1 Planken4 -- Balzers2 Balzers2 -- Vaduz5 Balzers2 -- Schaan4 Vaduz5 -- Schaan4 Schaan4 -- Triesenberg1 Schaan4 -- Vaduz6 Schaan4 -- Triesenberg2 Triesenberg1 -- Vaduz6 Triesenberg1 -- Triesen Triesenberg1 -- Balzers3 Triesen -- Balzers3 Triesen -- Balzers1 Triesen -- Schaan5 Vaduz6 -- Schaan5 Triesenberg2 -- Schaan5 }

Compiling this, we get the graph

Now, with this it is an easy job to get the adjacency graph for the communes. We can just delete all numbers in the above dot file. Graphing that, we get instead

Note, however, that the massive duplication of adjacency edges makes this rather hard to read. So we can just amalgamate all those edges into one single edge each. So in the end, the Liechtenstein graph turns out to be

Now, as Brian points out, there is a 5-clique in this map, given by Schaan, Balzers, Vaduz, Planken, Triesenberg.

*Edited*: Michael Lugo pointed out in the comments that my exclusion criterion for 6-cliques is obviously and trivially false. Discussion below here changed appropriately

If there were a 6-clique in the map, there would have to be 6 communes each of which have at least 5 edges connected to them. We can construct the table of degrees for all communes, to see whether this helps:

Balzers: 5

Eschen: 6

Gamprin: 5

Mauren: 2

Planken: 6

Ruggell: 2

Schaan: 7

Schellenberg: 3

Triesen: 4

Triesenberg: 5

Vaduz: 7

So, we have enough edges in Balzers, Eschen, Gamprin, Planken, Schaan, Triesenberg and Vaduz. This gives us 7 candidates for a 6-clique. Thus if two of these have too many edges outside this group, we know that there cannot be a 6-clique in the commune-graph.

Now note that Triesenberg borders to Triesen, so at most 4 of those 5 edges can be within a 6-clique. Also, Gamprin borders to Ruggell, so at most 4 of Gamprin’s 5 edges can be within a 6-clique. Thus the graph contains no 6-cliques.

Does this, though, mean that we can construct a 5-coloring of the graph? Try this on:

I would recolor the Liechtenstein map using this color choice, but I haven’t gotten around to installing a decent picture editing program just yet. That’ll have to wait.

To have a 6-clique, you’d need 6 nodes each with at least 5 edges, right? (That is, each node would have to connect to each of the other nodes in the clique.) Or am I missing something?