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.

For example, consider this graph. What are some common methods for determining whether the graph has a Hamiltonian circuit? After trying to find one, I'd conclude that it doesn't, but I don't know how to argue why it doesn't.

Any insight on the topic would be great; thanks for the help!

share|improve this question
1  
I think its part of en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems ; so there is no easy way to answer. –  ulead86 Nov 27 '12 at 10:33
1  
More precisely, there are no known efficient methods for all types of graphs. However, special types of graphs exists where they are known to have Hamiltonian circuits. One elementary, general example are graphs with $>2$ vertices and each vertex has $\geq n/2$ edges. –  Yong Hao Ng Nov 27 '12 at 14:08

1 Answer 1

up vote 1 down vote accepted

For your particular graph, here's why it can't be Hamiltonian. Consider the "square corners". If there exists an Hamiltonian cycle, this cycle must go through all of them. In particular it must go through every corner ($a,c,e,g,i,k,n,l$), so you know you have to go on all the edges on both squares (i.e. $(a,b), (b,c), (c,h), \dots, (d,a)$ and $(i,j), (j,k), (k,q), \dots, (o,i)$). There must also be at least two edges in the cycle connecting with the vertex $p$ (the one in the middle), for a total of $18$ edges. Since there are $17$ vertices, an Hamiltonian cycle must contain $17$ edges ; we've just shown you need at least $18$ to connect with every vertex, a contradiction.

The key in the argument is that there are a lot of vertices of degree $2$ in your graph ; that gives a lot of restrictions on the possible Hamiltonian cycles.

Hope that helps,

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.