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?



How many hamiltonian cycles can be removed from a complete directed graph before it becomes disconnected?
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](http://www.sciencedirect.com/science/article/pii/0095895680900441) 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. 


