Q:

Set of dominos with ends labeled with integers from 1 to 40 with all possible combinations represented. Longest proper sequence (chain) of dominos?

Consider a set of dominos in which the ends of each domino [are] labeled with distinct integers from 1 to 40 (inclusive) and all possible combinations are represented. A proper sequence of dominos is a line of dominos laid end-to-end adjacent ends having matching numbers. What is the longest proper sequence that can be formed with this set?

The question is from AIME 1998.

Amendment to Domino Types
I have excluded dominos of type $nn$, as these do not have ends labeled with distinct integers. This is no ordinary set of dominos!

Dominos are all of type $mn$ where $m\ne n$ and $1\le m,n\le40$. There are $\binom{40}{2}=780$ of these.
Now consider an undirected graph with $40$ nodes where each node is connected to every other node, and edges represent dominos. This is a clique with $780$ edges where each node has degree $39$. 
Since each node has odd degree, it is not possible to form an Eulerian path or circuit and so the longest proper sequence cannot include all dominos. In fact, the longest proper sequence can include at most two nodes of odd degree, meaning that at least $\frac{1}{2}38=19$ edges are "lost". So, if $L$ is the length of the longest proper sequence, then we have:
$$L\le780-19=761$$
I am unsure how to prove whether there is actually a proper sequence of this length, or not. 

A:

If you remove a maximum matching from $K_{40}$ the remaining graph has all degrees even, so it has an Eulerian cycle. You can "open up" this cycle at any vertex and at an arbitrary end add the domino you removed at that vertex.
So yes, the maximum length you arrived at is indeed attainable.

