Tanya Khovanova and Richard Stanley
On the left is a puzzle from the 2000 Qualifying Test for USA and Canada teams to compete in the world puzzle championship. A set of all 21 dominoes has been placed in a 7 by 6 rectangular tray. The layout is shown with the pips replaced by numbers and domino edges removed. Draw the edges of the dominoes into the diagram to show how they are positioned.
We would like to discuss the mathematical theory behind this puzzle using a toy example below. Only three dominoes: 1-1, 1-2, 2-2 are positioned on the board and the goal is to reconstruct the positioning:
Let’s connect adjacent numbers with segments to show potential dominoes and color the segments according to which domino they represent. The 1-1 edge is colored green, the 1-2 — blue, and the 2-2 — red. Now our puzzle has become a graph, where the numbers are vertices, the segments are edges, and the edges are colored. In this new setting, the goal of the puzzle is to find edges of three different colors so that they do not share vertices.
The next picture represents the line graph of the previous graph. Now the colors of the vertices correspond to different potential dominoes. Vertices are connected if the corresponding dominoes share a cell. In the new setting finding dominoes that do not share a cell is equivalent to finding an independent set. The fact that we need to use all possible dominoes means that we want the most colorful independent set.