Earth-Moon Problem
Earth-Moon Problem
167
In 1959, Gerhard Ringel proposed the Earth-Moon problem. Consider a map of an alien world, in which each country is a simply connected region. Around it revolves a moon divided into colonies of the countries, each a simply connected region. Colored maps of the world and moon must use the same color for a country and its colony, and different colors for both countries that share a border on the planet and colonies that share a border on the moon. What is the minimal number of colors needed [1]?
In 1980, Thom Sulanke found a pair of planar 11-region maps that had 50 of the possible 55 borders [1]. The missing five connections make a cycle (the graph) that requires three colors in order to have no two neighboring vertices of the same color. The six countries not in the cycle are all connected, making the graph, which needs six colors. All together, nine colors are required for the Sulanke Earth-Moon map.
C
5
K
6
For this Demonstration, all 1249 maximally triangular planar graphs on 11 vertices were studied, along with their complements. A total of 790 solutions of the type + were identified.
K
6
C
5