# Graph Theory - Hard Question -Finding for what values of n ≥ 2 is it possible to form a domino ring that uses all of the C(n,2) dominoes

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.

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?

-
What is your question? – utdiscant Dec 14 '12 at 7:57
I assume that you can do (a), and (b) is pretty easy, too. Where do you get stuck? – Brian M. Scott Dec 14 '12 at 7:57
Any hit or ideas , I know part a,but I am not sure about the rest. – Node.JS Dec 14 '12 at 7:58
When I see these kind of problems I am thinking how easy calculus / differential equations are ! – Node.JS Dec 14 '12 at 8:04

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$?

-
I have problem in part b - "Translate this Eulerian circuit into a ring of dominoes"- can you please explain more ? – Node.JS Dec 14 '12 at 8:12
@Hooman: Can you see how I translated the ring of dominoes in the picture into an Euler circuit? – Brian M. Scott Dec 14 '12 at 8:13
@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? – Brian M. Scott Dec 14 '12 at 8:41

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.

-
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. – nvcleemp Dec 14 '12 at 8:20