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.

How does one show that the following graph has no Hamiltonian cycle?


enter image description here


From N.S.'s comment I get that the problem really just reduces to the following simpler problem:


enter image description here


Actually, if you started at the top I guess that wouldn't really be the case... Maybe I should prove this using the $\wedge_{k=1}^np_i\implies q$ method:


enter image description here


Hmm... Maybe it can just be reduced to the following graph instead:


enter image description here

enter image description here


My own answer:

enter image description here

The subgraph $(a,b,c,d)$ is of critical importance here. Without doubt, a tracing along the graph must hit all of these points in the subgraph just mentioned either by exiting through $d$, and then re-entering through $b$ or vice versa. Either way, the tracer must make a choice upon re-entry to make a $(b,a)$-step or $(b,c)$-step, respectively $(d,a)$-step or $(d,c)$-step. Should the tracer take a $(b,a)$-step, respectively $(d,a)$-step, then the tracer will inevitably be trapped as proceeding to vertex $d$, respectively $b$, would mean the tracer hit that vertex twice. Now, if the tracer makes a $(b,c)$-step, respectively $(d,c)$-step, then the tracer will similarly be trapped as the proceeding vertex will have been traced upon twice. Thus, the graph cannot contain a Hamiltonian cycle.


share|improve this question
    
The upper (or lower) triangle also immediately shows that there is no Hamiltonian cycle. –  Tomas Aug 2 '13 at 22:53
    
I don't know if it makes it easier, but you could reduce it to a 3-SAT problem and show that all clauses can't be satisfied. –  kba Aug 2 '13 at 22:57
    
Here, the central line must be crossed. –  Trancot Aug 2 '13 at 23:03
    
You don't need a start point. The triangle`` at the top must be part of a cycle, same for the triangle`` at the bottom. But a cycle cannot contain a strictly smaller cycle. –  N. S. Aug 2 '13 at 23:03
    
Just color the edges which pass through the vertices of degree 2 with red, then you`ll see the solution..... –  N. S. Aug 2 '13 at 23:04
show 3 more comments

1 Answer 1

up vote 3 down vote accepted

Hint Assume by contradiction that the graph has a Hamiltonian cycle. Then the cycle must contain the four vertices of degree $2$ and there is only one way to visit each of those. Those give you 8 edges in the cycle, but for obvious reasons those 8 edges are not part of one cycle....

Added I argued above that the red edges below must be part of the Hamiltonian cycle. Then the Hamiltonian cycle would contain two smaller $4$-cycles, which is impossible (a cycle cannot contain a smaller cycle as a subgraph).

Pic

share|improve this answer
    
I bet there is a clever way to reduce this substantially... –  Trancot Aug 2 '13 at 22:57
    
Something like, all four points on a circle can't be hit with only two alternating exits without hitting a point twice... –  Trancot Aug 2 '13 at 22:57
    
@Trancot What do you mean reduce? The cycle must contain the 4 cycle at the top and the 4 cycle at the bottom. How can a cycle contain two cicles? –  N. S. Aug 2 '13 at 23:02
    
@Trancot If you have problems seeing the solution, which should be obvious from my hint, please label the vertices on your figure so I can refer to them.... –  N. S. Aug 2 '13 at 23:06
    
I see what you're saying, but why can't I show it for the reduced graph? –  Trancot Aug 2 '13 at 23:11
show 2 more comments

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.