Number of ways a handshaking can take place

Question

There is a group of 9 people. Each person shakes hands with exactly two others. I need to consider 2 handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. I need to find the number of such arrangements possible. The condition which is given is troubling. Can anyone help me with a simple combinatorial solution for this

Answer 1

The graph will be a union of cycles. The sizes of these cycles add up to $9$. As every cycle has size at least $3$, there are only four possibilities:

One cycle of lenght $9$.

Two cycles of lengths $3,6$.

Two cycles of lengths $4,5$.

Three cycles of lengths $3,3,3$.

Each of these four cases lead to a simple combinatorial problem. I show you the first and the last cases, you can finish the rest.

Preliminary calculation: Given $k\geq 3$ people, there are $(k-1)!/2$ ways to form a $k$-cycle out of them. Indeed, there are $(k-1)!$ cyclic orders of them, and each cyclic order defines the same cycle graph as the reverse cyclic order, and there are no other coincidences.

First case: the graph is a $9$-cycle. There are $(9-1)!/2=20160$ ways to make them form a $9$-cycle.

Last case: the graph is a union of three $3$-cycles. There are $\frac{9!}{(3!)^3\cdot 3!}=280$ ways to partition the $9$ people into three groups of $3$, and this uniquely determines a solution, as three people form a uique $3$-cycle.

Have fun with the rest of the proof, no new idea is needed.