Domino Trains Questions A train is an end-to-end arrangement of dominoes such that the adjoining halves of neighboring dominoes have the same number of dots.
A "double-$n$'' domino set has one of each possible domino using integers from $0$ to $n$, where order is not a distinguishing feature (so there aren't separate $0$-$2$ and $2$-$0$ dominoes, for example). 
Let $f(n)$ be the smallest number of trains that can be formed from the dominoes in a double-$n$ set, such that each domino is used in exactly one train. What are the values of $f(12)$ and $f(15)$?

How can I approach this problem with graph theory?
 A: This question really asks which complete graphs have an Eulerian cycle. For the complete graphs with an Eulerian cycle the answer is 1. For the complete graphs without an Eulerian cycle you need to find a decomposition in a minimal number of paths.
The dominoes of the form $i,i$ can be squeezed in at any moment you visit vertex $i$.
Can you take it from there??
One more hint: in the complete graphs without an Eulerian cycle, every vertex of odd degree must be endpoint of a path.
A: We need to look at Eulerian paths, and use the well-known result about them using odd and even vertices. This makes $f(12)=1$ and $f(15)=8$.
The trains are fairly basic in the odd case (an even number of vertices) - we 'disconnect' $\dfrac{k+1}{2}$ single edge disjoint graphs, the remaining graph is Eulerian and can have a path joined to it to make a train, the rest form individual trains.
A perhaps more interesting answer can be arrived at by defining a train as a rotationally symmetric path for the complete graph, for example for $n=8$ we have:

If we rotate the image four times we arrive at:

which gives us the four minimum trains as required.
