0
$\begingroup$

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?

  • 0
    What do you mean by "Hamiltonian cycle of degree 2"?2012-09-11
  • 0
    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: http://upload.wikimedia.org/wikipedia/commons/6/60/Hamiltonian_path.svg2012-09-11
  • 0
    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.2012-09-11
  • 0
    Ah right. I mean that the Hamiltonian cycle is such that every vertex in the cycle has degree 2, and by edges in this case it is when you "go" from one vertex to another in your cycle that you draw an edge between them. This shouldn't violate the "edge disjoint" pre-requisite as each Hamiltonian cycle will use completely different edges in its path. Hopefully I'm making sense, let me know if not.2012-09-11
  • 2
    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.2012-09-11
  • 0
    Ah yes, I see now. Because you visit each vertex only once it must have degree two, because you enter and leave it. Wish I realised that earlier, thanks!2012-09-11
  • 0
    Ok so, bearing that in mind, is my proof correct so? Note that I'm writing the n(n-1)/2 edges as the sum of the disjoint edges used in each distinct Hamiltonian cycle path.2012-09-11
  • 1
    "...and we can split our graph into individual Hamiltonian cycles..." You are assuming the very thing you wish to prove.2012-09-11
  • 0
    Austin, what I mean to show is that my proof for "n must be odd" relies on the assumption that we can split Kn into individual Hamiltonian cycles. However, I must prove the assumption first, because if it is false then of course my proof for "n must be odd" is invalid. In my OP I'm asking how to prove my assumption, but fortunately in the comments it was made clear that it is true and why that is so (by Grapthth).2012-09-11
  • 0
    I think your statement should be "We can write $K_n$ as the disjoint union of Hamiltonian cycles if and only if $n$ is odd." The "only if" part is easy: Were $n$ even, $K_n$ would be regular of odd degree, and so couldn't possibly be represented as the union of cycles. The "if" part is where the meat is.2012-09-12
  • 0
    Also, you can use @Username to let Username know you are replying to him/her. I have not been doing so with you, because the poster of a question is notified of all activity.2012-09-12
  • 0
    That the complete graph on an odd number of vertices can be decomposed into edge-disjoint Hamiltonian cycles was proved by Walecki in the 1890s. A websearch might turn up a proof. A reference is D.E.Lucas, Recreations Mathematiques, vol. II, Gauthiers Villars, Paris, 1892.2012-09-12

1 Answers 1

5

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 <span class=$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.