# How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways can you seat 5 people around a round table so that the people sitting to the left of any person is different in each seating arrangement?"

Here is a snap solution: For seating arrangements of $N$ people consider a directed graph with $N$ vertices and two opposite arcs connecting every pair of distinct vertices. Every hamiltonian cycle in that graph corresponds to a seating arrangement, where a directed edge corresponds to ''sitting to the left''. Call two hamiltonian cycles "intersecting" if they share a directed edge. The problem boils down to finding the maximal set of pairwise non-intersecting hamiltonian cycles. Since every vertex has $N-1$ outgoing edges the upper bound is $N-1$.

And here comes the error: Since hamiltonian cycles don't break a complete graph into disconnected components, we conjectured that the same is true for a set of non-intersecting hamiltonian cycles and therefore the above upper bound is exact.

However, a small experiment with $N=4$ demonstrates that the above conjecture is not true: removing any 2 hamiltonian cycles from a complete directed graph with 4 nodes breaks it into 2 disconnected components with 2 nodes each. Therefore the answer for $N=4$ is $2$, not $3$, and the above arguments leads only to an upper bound rather than an exact answer.

Thus the question: how does one compute the maximum number of non-intersecting hamiltonian cycles in a complete directed graph that can be removed before the graph becomes disconnected?

• Another snap solution: for 5 people and person A , any 5 arrangements must have at least one person P appearing at least twice on A's left. – The Masked Avenger Feb 17 '15 at 18:03

I will rephrase your question slightly. Let $K_{n}^{*}$ be the directed graph with $n$ vertices and two oppositely directed edges for each pair of vertices. Your question is then the following.
What is the maximum number of edge-disjoint directed Hamiltonian cycles of $K_{n}^{*}$?
For $n=2k+1$ odd, it is an old theorem of Walecki that $K_n$ can be decomposed into $k$ Hamiltonian cycles, and hence $K_n^*$ can be decomposed into $2k$ directed Hamiltonian cycles.
For $n=2k$ even, you are right to note that for $n=4$ we cannot achieve the upper bound of $n-1.$ One can also check that we cannot achieve the upper bound for $n=6$. However, Tilson proved that for even $n \geq 8$, $K_n^*$ can de decomposed into $n-1$ directed Hamiltonian cycles.
This completely answers your question. Namely, $n=4$ and $n=6$ are the only exceptions.