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?