1
$\begingroup$

A domino is a $2\times1$ rectangle. On each half of the domino is a number denoted by dots. In the figure, we show the ten dominoes whose pairs of numbers correspond to pairs chosen from $\{1,2,3,4,5\}$ (we do not include dominoes where the numbers are the same). Notice that we have arranged the ten dominoes in a ring so that where two dominoes meet, they show the same number.

a domino ring

Of interest to us is the following question: for what values of $n \geq 2$ is it possible to form a domino ring that uses all of the $C(n,2)$ dominoes that correspond to the pairs from $\{1,2,\ldots,n\}$. Let us solve the question by viewing it as a graph problem.

a. Recall that $K_n$ is the complete graph on $n$ vertices. Please draw $K_5$, naming your vertices $1,2,3,4,5$.

b. Write down an Eulerian circuit of $K_5$. Translate this Eulerian circuit into a ring of dominoes using pieces shown in the example. Conversely, starting with the example above, describe the corresponding Eulerian circuit of $K_5$.

c. Briefly argue that there is a bijection between the Eulerian circuits of $K_5$ and the domino rings that can be formed from the $C(5,2)$ dominoes above.

d. Regarding part (c), for what values of $n$ is it possible to form a domino ring using all $C(n,2)$ dominoes that correspond to the pairs from ${1,2,\ldots,n}$? Why?

  • 0
    When I see these kind of problems I am thinking how easy calculus / differential equations are !2012-12-14

2 Answers 2

2

HINTS: You need two main ideas to do this problem. The first is the correspondence between Euler circuits of $K_n$ and domino rings using the $\binom{n}2$ possible dominoes on the set $\{1,\dots,n\}$. For the ring in the picture, the Euler circuit of $K_5$ (with vertices labelled $1,2,3,4$, and $5$) is $1,2,3,4,5,3,1,4,2,5$, and back to vertex $1$; do you see how I got this circuit? Once you see what the correspondence is, explaining why it’s a bijection shouldn’t be too hard.

The second is the result that a graph has an Euler circuit iff it has no vertex of odd degree. What’s the degree of every vertex of $K_n$?

  • 2
    @Hooman: I’ll add a bit to that. Think of each edge in an Euler circuit of $K_5$ as a domino. If the edge is between vertices $i$ and $j$, what numbers do you think should be on the domino?2012-12-14
0

Since Eulerian circuits exist if and only if all vertices have an even degree, and there is, as you explained, a one-to-one correspondence between domino rings and Eulerian circuits in $K_n$, I would say that a domino ring can only be formed if and only if $n$ is odd.

  • 0
    OK, I assumed that you already had parts (a) through (c) worked out, and were stuck on the why in part (d). To explain the one-to-one correspondence between Eulerian circuits and domino rings, I think Brian M. Scott's answer already gives the correct clues.2012-12-14