How many ways are there to shake hands? 
In a group of $9$ people, each person shakes hands with exactly $2$ of the other people from the group. Let $X$ be the number of possible ways to perform these handshakes. Take $2$ handshake patterns (arrangements) distinct if and only if at minimum $2$ people who shake hands under one pattern (arrangement) don't shake hands under the other pattern (arrangement). Find $X$.

I think casework is the way to go. 
$A$ shakes with $B$ & $C$. 
$D$ shakes with $E$ & $F$.
$G$ shakes with $H$ & $I$. 
Perhaps I could use a recurrence relation, but I don't see a possible way. 
In total there are: 
$$\binom{9}{3} \cdot \binom{6}{3} \cdot \binom{3}{3} = 1680$$
Ways to choose groups of three people. 
But I dont anything else to this problem, and clearly this is the wrong answer. 
Hints only please!
 A: The handshakes can be modelled by a graph, you want to find the number of $2$-regular graphs on nine vertices.
It is known $2$-regular graphs have cycles as connected components.
There are three options for the number of connected components:
One connected component:
In this case the graph is a cycle on $9$ vertices, the cycle can be viewed as a permutation starting with $1$ listing vertices in order. There are $8!$ such permutations, but they give us each cycle twice (once in each order).
Hence there are $\frac{8!}{2}=20,160$ such cycles. It will be good to take note of the following formula: there are $\frac{(k-1)!}{2}$ ways to make a cycle with $k$ vertices.
Two connected components:
We have to subdivide depending on the sizes of the two components:
$3$ and $6$: first choose the three vertices in $\binom{9}{3}$ ways, after the above formula  gives us $\frac{2!}{2}\frac{5!}{2}$ ways to form the cycles. So there are $\binom{9}{3}\frac{2!}{2}\frac{5!}{2}=5,040$ cycles of this kind.
$4$ and $5$: first choose the four vertices in $\binom{9}{4}$ ways,after the above formula gives us $\frac{3!}{2}\frac{4!}{2}$ ways to form the cycles. So there are $\binom{9}{4}\frac{3!}{2}\frac{4!}{2}=4,536$
Three connected components:
There are $\binom{9}{3,3,3}$ ways to split the nine vertices into the three groups. Of course this distinguishes each of the factor, so in fact the answer is $\binom{9}{3,3,3}\frac{1}{3!}=280$
So final answer is $20,160+5,040+4,536+280=30,016$
