# Are there any efficient ways to tell if a graph has a Hamiltonian circuit?

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!

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