Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Where did you find this problem? –  Aryabhata Dec 27 '10 at 17:53
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. –  Hans Parshall Dec 28 '10 at 2:47

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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