Q:

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?

A:

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

