Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Hooman Dec 14 '12 at 7:58
    
When I see these kind of problems I am thinking how easy calculus / differential equations are ! –  Hooman Dec 14 '12 at 8:04
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
    
I have problem in part b - "Translate this Eulerian circuit into a ring of dominoes"- can you please explain more ? –  Hooman 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
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? –  Brian M. Scott Dec 14 '12 at 8:41
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.