The empire problem, also known as the 
-pire problem, asks for the maximum number of colors needed
to color countries on a planar map such that no two
countries sharing a common border have the same color, in the case where each country
consists of at most 
disjoint regions. For 
,
this is the usual four-color theorem. Heawood
(1890) showed that 
colors are sufficient, and for the case 
, 12 colors are also necessary
(Gardner 1997; Frederickson 2002, pp. 31-32).
The Earth-Moon problem imposes the additional restriction that one region of each country lies on each of two separate maps. Its required number of colors is known to lie between 9 and 12, so the 12-color lower bound for unrestricted two-region empires does not establish the answer to the Earth-Moon problem (Archdeacon, online version, pp. 32-33).
In the illustrated map, each empire consists of the two regions bearing the same number. Every pair of empires shares a border, so all 12 colors are required.
Scott Kim's symmetric 12-empire map (Jackson and Ringel 1984, p. 146) can be realized on a regular dodecahedron by dividing each face into a pentagon and a quadrilateral (E. Pegg, Jr., pers. comm., Oct. 27, 2026). Matching numbers and colors identify the two regions of each empire, on different faces. The opposite views show all 24 regions, with thicker lines marking the original edges.
