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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
answered Jul 29 '14 at 12:34
-
$\begingroup$ Thank you for the answer. Can please explain me the proof for answer (n-2)/2. $\endgroup$ – Krishnaprasad Jul 29 '14 at 15:01
$\begingroup$
$\endgroup$
Hint: A necessary condition to partition $E(K_n)$ into edge-disjoint Hamiltonian cycles is that $n$ divides the number of edges.
-
$\begingroup$ Well, the decomposition is only required to be edge-disjoint, not complete. $\endgroup$ – Hagen von Eitzen Jul 29 '14 at 11:22
$\begingroup$
$\endgroup$
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.
