At the moment I'm trying to prove the statement:

$K_n$ is an edge disjoint union of Hamiltonian cycles when $n$ is odd.

($K_n$ is the complete graph with $n$ vertices)

So far, I think I've come up with a proof. We know the total number of edges in $K_n$ is $n(n-1)/2$ (or $n \choose 2$) and we can split our graph into individual Hamiltonian cycles of degree 2.

We also know that for n vertices all having degree 2, there must consequently be $n$ edges. Thus we write $n(n-1)/2 = n + n + ... n$ (here I'm just splitting $K_n$'s edges into some number of distinct Hamiltonian paths) and the deduction that $n$ must be odd follows easily.

However, the assumption I made - that we can always split $K_n$ into Hamiltonian paths of degree 2 if $K_n$ can be written as a disjoint union described above - I'm having trouble proving. I've only relied on trying different values for $n$ trials and it hasn't faltered yet. So, I'm asking:

If it is true, how do you prove that if $K_n$ can be split into distinct Hamiltonian cycles, it can be split in such a way that each Hamiltonian cycle is of degree 2?

  • $\begingroup$ What do you mean by "Hamiltonian cycle of degree 2"? $\endgroup$ – Austin Mohr Sep 11 '12 at 17:16
  • $\begingroup$ Austin - by Hamiltonian cycle, I mean a path on a graph that goes around the such that it visits every vertex only once. Hopefully this illustrates what I mean: upload.wikimedia.org/wikipedia/commons/6/60/… $\endgroup$ – user64219 Sep 11 '12 at 17:19
  • $\begingroup$ Yes, that is the typical definition of Hamiltonian cycle. Your last sentence includes the phrase "each Hamiltonian cycle is of degree 2", which is unknown to me. $\endgroup$ – Austin Mohr Sep 11 '12 at 17:21
  • 2
    $\begingroup$ For any cycle, all vertices in it are of degree 2. So, if you say cycle, no need to say anything about degree 2. That's why he was asking. In fact, a graph $G$ is a cycle if and only if it is both connected and all vertices are degree 2. $\endgroup$ – Graphth Sep 11 '12 at 17:44
  • 1
    $\begingroup$ "...and we can split our graph into individual Hamiltonian cycles..." You are assuming the very thing you wish to prove. $\endgroup$ – Austin Mohr Sep 11 '12 at 18:43

What you are looking for is a Hamilton cycle decomposition of the complete graph $K_n$, for odd $n$.

An example of how this can be done (among many other results in the area) is given in: D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics, vol. 346, Cambridge University Press, 2007, pp. 67–97.

For odd $n$, let $n=2r+1$, take $\mathbb{Z}_{2r} \cup \{\infty\}$ as the vertex set of $K_n$ and let $D$ be the orbit of the $n$−cycle

\[(\infty, 0, 1, 2r − 1, 2, 2r − 2, 3, 2r − 3,\ldots , r − 1, r + 1, r)\]

under the permutation $\rho_{2r}$ [Here $\rho_{2r}=(0,1,\ldots,2r-1)$]. Then $D$ is a decomposition of $K_n$ into $n$-cycles.

Here is the starter cycle for a Hamilton cycle decomposition of $K_{13}$, given in the paper:

The starter cycle for a Hamilton cycle decomposition of $K_{13}$

If you rotate the starter, you obtain the other Hamilton cycles in the decomposition.

The method of using a "starter" cycle under the action of a cyclic automorphism is typical in graph decomposition problems.


Your Answer

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