A Puzzle on the Petersen

Prepare 10 equal rectangular pieces of paper, say, the standard 3"×5" cards. Draw on the cards the words (one word per card) HEN, HUT, WIT, SAW, CAR, CUB, MOB, DIM, RED, SON. The task is to arrange the cards in a rectangular closed chain in the manner of domino. In the chain, any two adjacent words must share a common letter.

The above may serve to demonstrate a possible arrangement. However, note that as it is it is lacking. The words SON and RED, although adjacent, do not have a letter in common. Therefore, it's not a valid configuration.

Repeat the same problem with the cards SON and HUT replaced by SUN and HOT. (Try both with a Java applet.)

Discussion

Discussion

The first problem has no solution, the second problem -- with a pair of cards replaced -- does. To see why, let's create two graphs, one per problem. The cards will correspond to the vertices, with two vertices connected by an edge if they share a letter.

Each of the problems is equivalent to finding a Hamiltonian path on the corresponding graph. The first one, known as the Petersen graph, has no Hamiltonian circuit, the second does.

Why the Petersen graph does not have Hamiltonian circuits? Simple. The graph has 10 nodes and 15 edges. The edges could be split into three groups: external (1-2, 2-3, 3-4, 4-5, 5-1), middle (1-6, 2-7, 3-8, 4-9, 5-10), and internal (6-7, 7-8, 8-9, 9-10, 10-6). A Hamiltonian circuit would pass through 10 vertices and comprise 10 edges.

There is a fundamental mathematical fact known as the Pigeonhole principle: if there are more pigeons than holes, there is a hole shared by at least 2 pigeons. If 10 items are split into 3 sets, at least one of the sets contains at least 4 items.

A Hamiltonian circuit on the Petersen graph, if existed, would contain 4 edges of at least one of the three groups: external, middle, or internal. Let's check that this is impossible.

For example, assume that the Hamiltonian circuit contains 4 edges from the external group. (Quite obviously it can't contain all 5 edges), the edge 3-4 excluded. Automatically, edges 1-6, 2-7, 5-10 could not be on the path, for otherwise, three egdes would meet at one of the nodes 1, 2, or 5. On the other hand, the egdes 3-8 and 4-9 must be a part of the circuit, for otherwise, there would not be a circuit in the first place. It follows that the circuit should contain 4 internal edges. But - try and see - there is no path between nodes 8 and 9 that is 4 edges long.

You may want to play with the graph to verify that the assumptions that the circuit contains 4 internal or 4 middle edges also lead to a contradiction.

William McWorter found a different proof that is still based on the Pigeonhole principle. This approach has an advantage of having only to consider one case.

If the Petersen graph has a Hamiltonian circuit, then the edges of the Petersen graph can be colored in three colors (the edges are 3-colored if the edges are colored in 3 colors and no two edges with a common node has the same color). Just color alternate edges of the Hamilton circuit red and white and color the edges not on the circuit blue. Hence, to show that the Petersen graph has no Hamiltonian circuit, it suffices to show that the edges of the Petersen graph cannot be 3-colored.

Assume that the edges of the Petersen graph can be 3-colored. Then, by pigeonhole, the 5 outer edges must have two edges the same color, say wlog⁽¹⁾, 2-3 and 4-5 are red. Then edge 3-4 has a different color, say white; whence edges 3-8 and 4-9 are colored blue. Since edges 1-2 and 1-5 must be colored white and blue or blue and white, resp., edge 1-6 must have color red. But then edges 6-8 and 6-9 must have colors different from red (the color of 1-6) and different from blue (the color of 3-8 and 4-9). Hence both have color white, contradiction.

References

1. Tom Rodgers, A Scrub Tile Puzzle, in Puzzler's Tribute, D. Wolfe and T. Rodgers (eds.), A K Peters, 2002

⁽¹⁾ wlog = "without loss of generality".