Earth-Moon Problem

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.
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.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


A related unsolved problem involves the geometric thickness of a graph. With all edges being straight lines, what is the minimal number of colors needed so that no two edges of the same color cross? The Paley-13 graph has geometric thickness 2, as shown below.
Using rectangle visibility graphs, geometric thickness-2 graphs with vertices and edges are known. The proven maximum for vertices is edges, but no examples are known. The graphs in this Demonstration use 11 vertices and 50 edges. If a combined form can have two edges removed so that no two edges of the same color cross, then that would provide a solution.
[1] N. Hartsfield and G. Ringel, Pearls in Graph Theory, Mineola, NY: Dover Books, 2003, p. 204.
[2] D. Eppstein. "The Geometry Junkyard: Layered Graph Drawing." (Sep 22, 2015) www.ics.uci.edu/~eppstein/junkyard/thickness.
[3] B. Jackson, "Variations on Ringel's Earth–Moon Problem," Discrete Mathematics, 211(1–3), 2000 pp. 233–242. doi:10.1016/S0012-365X(99)00278-2.
[4] J. Battle, F. Harary, and Y. Kodama, "Every Planar Graph with Nine Points Has a Non-planar Complement," Bulletin of the American Mathematical Society, 68, 1962 pp. 569–571. www.ams.org/journals/bull/1962-68-06/S0002-9904-1962-10850-7/S0002-9904-1962-10850-7.pdf.
[5] E. Mäkinen and T. Poranen. "An Annotated Bibliography on the Thickness, Outerthickness, and Arboricity of a Graph." (Sep 22, 2015) www.sis.uta.fi/~tp54752/pub/thickness-bibliography/thickness-bibliography.pdf.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2017 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+