Longest possible subsequence present with a given condition

Question

Let a Domino represent an ordered pair of distinct positive integers. A proper sequence of dominos is a list of distinct dominos in which the first coordinate of each pair after the first equals the second coordinate of the immediately preceding pair, and in which $(i,j)$ and $(j,i)$ do not both appear for any $i$ and $j$. Let $D_{40}$ be the set of all dominos whose coordinates are no larger than $40$. How can I find the longest proper sequence of dominos using the dominos of $D_{40}$?

Answer 1

First draw a domino set of $40$ points which are connected to each other. These connections represent the dominoes.

Then we have all the even number of segments coming from each connected point except for $0$ and $2$ because it has an odd number of segments from the point. Note that every time when we go to vertex, it means that we are leaving the vertex. So when we reach every vertex it is equivalent to adding $2$ more segments which means that the degree of each vertex should be even leaving the endpoints. Since there are $39$ segments coming from each point it is impossible to touch every segment.

But you can get up to $38$ on each segment because you go in to the point then out on a different segment. Counting going out from the starting and ending at the ending point we have $\dfrac{30\times40+2}{2}=761$