3
$\begingroup$

Given $K_n$ define sequence $S_4$: writing all vertices in order of traversing it by Euler circle

How many distinct Hamilton cycles are in this sequence $S$?

  • 0
    Where did you find this problem?2010-12-27
  • 1
    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.2010-12-28

3 Answers 3

3

It can certainly vary. As an Eulerean path uses all $\frac{n(n-1)}{2}$ edges and a Hamiltonian path uses $n$, you can't have more than $\frac{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

  • 0
    Wouldn't an Eulerian path use all $n(n+1)/2$ edges?2010-12-28
  • 0
    Obviously no segment, but I think this is talking about sequences of edges that make a Hamiltonian path.2010-12-28
  • 0
    @Hans Parshall: You are right. Fixed (I hope). Thanks2010-12-28
  • 0
    You fixed it better than I did.2010-12-28
3

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.

  • 0
    For even n, there aren't any Eulerian tours.2010-12-28
  • 0
    @Jacob: Yes, I meant we can get close... Edited. Thanks.2010-12-28
3

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

$K_5$

$$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$.