Question

A domino is a 1 x 2 rectangular tile with 0,1,2,...,6 dots on each half. In a 6. complete set of 28 dominos, each combination of numbers appears exactly once on the two halves of some domino. Show that the dominos can be laid end to end with adjacent halves containing the same number of dots.

Answer 1

We will be using a different representation to solve this problem. We will consider halves of the dominoes to be vertices, and the dominoes themselves to be edges between their halves. Thus, we have 7 vertices, and every possible edge including loops, to account for doubles. The graph will be as shown below:

Then, a walk on this graph represents a series of consecutive dominoes: for instance,
the walk 4 ∼ 2 ∼ 2 ∼ 6 traverses 3 edges, representing 3 dominoes, and we have
the series of dominoes

0 1 5 3 4

To visit each domino exactly once, we thus need to traverse each edge exactly once. That is to say, a sequence of all 28 dominoes satisfying the conditions given above is identical to an Eulerian walk on this graph. By inspection, every vertex of the above graph can be seen to have degree 8, so since every vertex is of degree 8, an Eulerian walk (or even an Eulerian cycle) can be constructed.