Consider the complete graph $\mathcal{G}_n$, over the set of vertices $\{1,2, \ldots, n\}$. To each domino $(i, j)$ in $D_n$, we associate the edge joining the two vertices $i, j$. In this way, to each edge in $\mathcal{G}_n$ we have associated exactly two dominoes $(i, j)$ and $(j, i)$, for some $1 \leq i \neq j \leq n$. A proper sequence of dominoes corresponds exactly to a path in $\mathcal{G}_n$ which visits every edge at most once. The problem asks for the length of the longest such path. We will use and prove the following:

> If a finite graph $\mathcal{G}$ is connected and each of its vertices has an even degree, there exists a closed path which visits all its edges exactly once. This closed path is called Eulerian.

We will prove this fact by induction on the number of edges of $\mathcal{G}$.

If $\mathcal{G}$ has 3 edges, then it is a triangle and the statement is obvious. Assume there exists a closed Eulerian path in any connected graph with all vertices of even degree having less than or equal to $m$ edges.

Let $\mathcal{G}$ be a connected graph with $m+1$ edges and all its vertices are of even degree. Let $\mathcal{P}$ be a longest path visiting each edge of $\mathcal{G}$ at most once.

Assume that $\mathcal{P}$ starts and ends at different vertices $v, v'$. Path $\mathcal{P}$ visits an odd number of edges incident to $v$. But the degree of $v$ is even. Then, there exists an edge $e$ incident to $v$ which is not visited by $\mathcal{P}$ and so, we can extend $\mathcal{P}$ with $e$. This contradicts the maximality of $\mathcal{P}$. Hence path $\mathcal{P}$ starts and ends at the same vertex.

Assume that there exists an edge $e$ not visited by $\mathcal{P}$ and let $v$ be a vertex incident to $e$ and $v_1$ a vertex visited by $\mathcal{P}$. Because $\mathcal{G}$ is connected, there exists a path from $v$ to $v_1$. Replace $v_1$ by the first vertex in this connecting path visited by $\mathcal{P}$. Let $\mathcal{G}'$ be the graph obtained by deleting from the graph $\mathcal{G}$ all edges visited by $\mathcal{P}$ and taking the connected component of $v_1$. Graph $\mathcal{G}'$ contains edge $e$ and has less than $m$ edges. Each vertex $v'$ of $\mathcal{G}'$ has even degree since path $\mathcal{P}$ has visited precisely an even number of edges incident to $v'$. Hence, there exists a closed Eulerian path $\mathcal{P}'$ in $\mathcal{G}'$. By considering in $\mathcal{G}$ the path starting at $v_1$ and walking along all the path $\mathcal{P}$ and then along all the path $\mathcal{P}'$ we obtain a longer path in $\mathcal{G}$ visiting each edge at most once. This contradicts the maximality of $\mathcal{P}$. This proves that edge $e$ does not exist and that $\mathcal{P}$ is Eulerian.

Back to our problem, we will consider two cases:

If $n$ is an odd number, the degree of each vertex of the complete graph $\mathcal{G}_n$ is $n-1$, even, and $\mathcal{G}_n$ is connected. So there exists a path visiting all the edges of $\mathcal{G}_n$ exactly once. Hence the longest proper sequence of dominoes that can be formed using the dominoes of $D_n$ uses all dominoes. It has length $\binom{n}{2} = \frac{n(n-1)}{2}$.

If $n$ is an even number, the degree of each vertex of the complete graph $\mathcal{G}_n$ is odd. Let $\mathcal{P}$ be a longest path visiting each edge at most once. For each vertex $v$ different from the starting and the ending vertices of $\mathcal{P}$, path $\mathcal{P}$ visits an even number of edges incident to $v$. So there exists at least one edge incident to $v$ not visited by $\mathcal{P}$. Because each edge is incident to two vertices, there exists at least $\frac{n-2}{2}$ edges not visited by $\mathcal{P}$. Hence the length of $\mathcal{P}$ is less than or equal to $\binom{n}{2} - \frac{n-2}{2} = \frac{n^2 - 2n + 2}{2}$.

Now, consider the graph $\mathcal{G}_n'$ obtained from $\mathcal{G}_n$ by deleting the edges between $1$ and $3$, $2$ and $3$, and $2i-1$ and $2i$, for $2 \leq i \leq \frac{n}{2}$. Graph $\mathcal{G}_n'$ is connected and all its vertices have even degree. So there exists an Eulerian closed path $\mathcal{P}'$ starting and ending at $3$. Extending path $\mathcal{P}'$ in $\mathcal{G}_n$ at the beginning with the edge between $1$ and $3$ and at the end with the edge between $2$ and $3$, we obtain a path $\mathcal{P}$ of length $\frac{n^2 - 2n + 2}{2}$ visiting each edge at most once. Hence the longest proper sequence of dominoes that can be formed using the dominoes of $D_n$ has length $\frac{n^2 - 2n + 2}{2}$.