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

Hope that helps,

-

Lets see if I can improve the answers. It is know for a Hamiltonian Graph that if I choose a group of vertexs that I will call S, then the number of connectec components of G\S is less or equal to |S| (being G our graph) . That means that if I choose a set of vertexs and remove them from my graph, then the number of connected components must be less than the number of vertexs of the set I created. So if you choose o,j,q,m and count the number of c.c. that remain you will find 6. Since S is only formed by 4 vertexs that gives us the proof that the graph is not Hamiltonian.

-

There isn't a Hamiltonian Cycle because there is no way to cycle through the outer square. Once you start on the outer square (whether you start the cycle or started elsewhere), there is no way to get all the vertices in the trace. Therefore, it has no Hamiltonian Cycle.

-