A new class has just been started, and there are $n$ people in this class that do not know each other. At each session they sit around a round table. They decided to change their adjacent persons in each session, so that all people come to know each other as soon as possible. What is the minimum number of sessions after which all people know each other?
To solve the above problem, I associated a graph to each session where the nodes are the persons and the neighbours to each person are connected to that person via an edge. So the degree of each node is $2$. Indeed, each session is a cycle which includes all nodes (persons) of the graph. So the question is how many spanning cycles exist in a complete graph that do not have any common edge? A common edge is not allowed since it represents a repeated neighbor for some person.
A complete graph with $n$ nodes has $\frac{n(n-1)}{2}$ edges and each cycle is going to include $n$ of these edges. So, I think if we are lucky and can use all of the edges to build such cycles then at most we can make $\frac{n-1}{2}$ of these cycles.
$1$. Is this argument valid?
$2$. Can we use all of the edges to make such cycles?
Best Answer
It is possible to partition all of the edges of the complete graph into Hamiltonian cycles whenever $n$ is odd. Furthermore, it is clearly impossible when $n$ is even, since in that case the number of edges is not a multiple of $n$.
First, partition an even order complete graph on $2m$ vertices into $m$ Hamiltonian paths, using the construction in this other answer. Then, add a new vertex, and close up each of these paths by connecting both ends to the new vertex. You now have $m$ Hamiltonian cycles with disjoint edges on the complete graph on $2m+1$ vertices.
I got this construction from Wikipedia, where it is attributed to Welecki. They give the following helpful illustration, for $n=9$.