Problem of the Week 1149
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. 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
© Copyright 2011 Stan Wagon. Reproduced with permission.