| (spoiler alert) Thanks a lot for the game. I really enjoyed it and it got me thinking about the coloring problem. I wonder if it could be interesting to also add some bits of the corresponding graph problem into the game. This might be able to make the coloring problem a bit less "mysterious", but not less interesting. Some shower thoughts: It's easy to see that if you start with an arbitrary "country map", you can easily convert it into a graph with the same coloring properties: Just draw a node into the center of each region, then, if two regions have a shared border somewhere, connect their nodes with an edge. The coloring problem is now the task of coloring all the nodes, so that no two nodes that are directly connected with an edge have the same color. The solution to that task is also easy to see: If you have n nodes where each nodes has edges to all the other nodes, then you need n colors. The more "missing" edges you have in the graph, the less colors you can get away with. (The location of the missing edges is important though: As soon as there a group of n fully connected nodes, you need at least n colors, no matter how many additional nodes and missing edges there are) Does that mean you can construct graphs that need 5 colors or more? Yes, just make the desired number of nodes and draw edges between all of them. So then, where does the limit of 4 come from? There it gets interesting: Because not every graph con be converted back into a country map: Only planar graphs, i.e. graphs where no edges cross if you lie it out on a plane have a corresponding country map, otherwise you'll get an "impossible geometry". So the coloring problem "really" shows that you can have at most 4 fully connected nodes in a planar graph - if you have graphs with more connections, you will always have at least two edges crossing, no matter how you arrange the nodes and edges on the plane. This might also explain why it is so hard to produce good visualisations for arbitrary graphs. An interesting question might be how the planar criterion works for other geometries, e.g. if you lay out the graph on a sphere or torus or multi-hole torus. Another aside: In real life, states are not always continous regions on a map. There are a lot of nations that have enclaves, oversea territories or for other reasons consist of more than one geographical region. So in theory, a "map of nation states" instead of a "map of regions" could represent a nonplanar graph and could have a coloring number greater than 4. I'm not sure if there is actually such a situation anywhere on the globe though. |