2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Well, the decomposition is only required to be edge-disjoint, not complete. $\endgroup$ – Hagen von Eitzen Jul 29 '14 at 11:22
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.