Number of edge disjoint Hamiltonian cycles in a complete graph with even number of vertices.

Question

In a complete graph with $n$ vertices there are $\frac{n−1}{2}$ edge-disjoint Hamiltonian cycles if $n$ is an odd number and $n\ge 3$. What if $n$ is an even number?

Answer 1

Since each Hamiltonian takes away two edges per vertex, an obvious upper bound for the even case is $\frac n2-1$. For the lower bound, use the following construction: If $n=2m+2$, let the vertices be $0,1,2,\ldots,n-2,n-1$. For $d=1,2,\ldots m$, we have a Hamiltonian cycle of all points except $n-1$ by making steps of length $d$ (i.e. there is an edge between $a$ and $a\pm d\bmod {n-1}$. To turn these into Hamiltonians for the full graph, note that for $k=0, 1, \ldots, m-1$ the edge $k\to 2m-k$ belongs to one of thes Hamiltonians, namely the one with step size $d=2k+1$ or $d=2m-2k$, whichever is $\le m$. Replacing this edge with $k\to n-1\to 2m-k$ we get a Hamiltonian cycle for the larger graoh, and all these are edge-disjoint.

Answer 2

Hint: A necessary condition to partition $E(K_n)$ into edge-disjoint Hamiltonian cycles is that $n$ divides the number of edges.

Answer 3

Show that $K_7$ has Hamiltonian graph. How many edge disjoint Hamiltonian cycles are there in $K_7$? List all the edge disjoint Hamiltonian cycles. is it eulerian graph.