Problem of the Week 1149

Doughnut King

The graph of king's moves on a 4×3 chessboard uses vertices to represent squares and edges for all legal king moves. There are 12 vertices, which look like this:

The problem: Color the edges of the king graph on a torus using 8 colors, so that edges that meet at a vertex get different colors.

On a torus the king (just like Mr. or Ms. Pac-Man) can leave the right edge and enter on the left, or exit the top and enter on the bottom. The diagram at left below duplicates 2, 3, 4, 5, 9 and quadruplicates 1 to show all the edges. Each of the 12 vertices has 8 neighbors, so you have 12 × 8/2 = 48 edges to color. The torus at right shows what the 3-dimensional board really looks like: the big dots are the centers of the squares.

© Copyright 2011 Stan Wagon. Reproduced with permission.