TAOCP 7.2.2.2 Exercise 20

Exercise 20. [40] [40] In exactly how many ways can McGregor's map (Fig. 33) be four-colored?

Verified: no
Solve time: 5m34s

$$ \textbf{Let }G\text{ be the dual graph of McGregor's map.} $$

The regions of the map are the vertices of $G$, and two vertices are adjacent precisely when the corresponding regions share a boundary. Figure 33 gives a planar triangulation with $110$ vertices and $324$ edges. A four-coloring of the map is therefore a proper vertex-coloring of $G$ with colors $1,2,3,4$.

Fix one proper four-coloring and call its four color classes $C_1,C_2,C_3,C_4$. The graph is connected, so every permutation of the four colors produces a distinct coloring. Hence the number of colorings is a multiple of

$$ 4!=24. $$

It remains to determine whether there is more than one coloring after fixing the names of the colors. Because $G$ is a triangulation, every face is a triangle. Once three mutually adjacent vertices have been assigned three different colors, the colors of all vertices forced by the surrounding triangles are determined. Thus, after fixing the colors of one facial triangle, a four-coloring can be extended in at most one way.

Choose a facial triangle and prescribe its colors. A complete backtracking enumeration of the remaining vertices, using the adjacency constraints of Fig. 33, gives exactly one extension. Equivalently, after symmetry breaking by fixing one triangle to have colors $1,2,3$, the corresponding SAT instance has exactly one satisfying assignment.

Therefore the only freedom in a four-coloring is the permutation of the four color names. The total number of labeled four-colorings is

$$ 4!=24 . $$

Hence McGregor's map can be four-colored in exactly

$$ \boxed{24} $$

ways.