# Euler circle and Hamilton cycles

Given Kn define sequence S: writing all vertices in order of traversing it by Euler circle

How many distinct Hamilton cycles are in this sequence S?

-
Where did you find this problem? – Aryabhata Dec 27 '10 at 17:53
I think the best answer, based upon the answers below, is that it depends on the sequence you're talking about. As stated, the sequence isn't well defined. – Hans Parshall Dec 28 '10 at 2:47

It can certainly vary. As an Eulerean path uses all n(n-1)/2 edges and a Hamiltonian path uses n, you can't have more than (n-1)/2. Can you have that many? There aren't any Eulerean paths if n is even and >2. Depending upon your definition, I can define an Eulearean path that has no segment that is Hamiltonian

-
Wouldn't an Eulerian path use all $n(n+1)/2$ edges? – Hans Parshall Dec 28 '10 at 1:07
Obviously no segment, but I think this is talking about sequences of edges that make a Hamiltonian path. – JSchlather Dec 28 '10 at 1:38
@Hans Parshall: You are right. Fixed (I hope). Thanks – Ross Millikan Dec 28 '10 at 1:38
You fixed it better than I did. – Hans Parshall Dec 28 '10 at 4:12

The question does not seem to be very precise.

In any case,

It is well known that $K_{2k+1}$ can be decomposed into $k$ hamiltonian cycles.

So we can find an Euler tour with exactly $\dfrac{n-1}{2}$ hamiltonian cycles for odd $n$.

For even $n$, we can do an "incomplete tour" with $\dfrac{n}{2}-1$ (See link above) hamiltonian cycles.

-
For even n, there aren't any Eulerian tours. – JSchlather Dec 28 '10 at 1:51
@Jacob: Yes, I meant we can get close... Edited. Thanks. – Aryabhata Dec 28 '10 at 1:52

There aren't necessarily any Hamiltonian cycles in your sequence.

As Ross already pointed out, provided $n$ is even and $n > 2$, then all vertices have odd degree and no Eulerian circuit exists. So, we need only worry about when $n$ is odd and $n > 3$.

For $K_5$ arranged as in the picture, an Eulerian circuit with no Hamiltonian cycles is given by

$$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 1 \rightarrow 5 \rightarrow 3 \rightarrow 1.$$

Now suppose $K_{n-2}$ has an Eulerian circuit with no Hamiltonian cycles. First label the vertices of $K_n$ as $1, \ldots, n$. Our Eulerian circuit with no Hamiltonian cycles for $K_n$ is given by first travelling $1 \rightarrow 2$, then travelling the Eulerian circuit with no Hamiltonian cycles for $K_{n-2}$ across the vertices $2, \ldots, n-1$, arriving back at $2$. Then for $k = 2, 4, 6, \ldots, n - 3$, we travel $$k \rightarrow n \rightarrow k + 1 \rightarrow 1 \rightarrow k + 2.$$ Finally, we travel $n-1 \rightarrow n \rightarrow 1.$

It follows from induction that $K_n$ contains an Eulerian circuit with no Hamiltonian cycles for all odd $n$.

-