Problem of the Week 1149Doughnut King
The graph of king's moves on a
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. PacMan) 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
© Copyright 2011 Stan Wagon. Reproduced with permission.
