A graph G on n vertices is Hamiltonian if there exists a cycle in G containing each of the n vertices once.

The IsHamiltonian(G) function returns true if the graph is Hamiltonian and false otherwise.  If G is Hamiltonian and a name C is specified as a second argument, then C is assigned a list of vertices of a Hamiltonian cycle of the graph starting and ending with the first vertex in G. For example, if the graph G is the triangle graph created with Graph({{1,2},{1,3},{2,3}}), the cycle is output as .

The algorithm works for directed graphs and it ignores the edge weights of weighted graphs.

The algorithm first checks whether G is disconnected or whether it has any articulation points.  If so, then G is not Hamiltonian. Then it tests whether the minimum degree of G is at least  where  is the number of vertices.  If so G is Hamiltonian.  Then, if G is not too sparse, the algorithm checks whether the independence number of G is greater than . If so, then G is not Hamiltonian.  Failing these checks, the algorithm does a simple exhaustive search for a Hamiltonian cycle using depth-first-search. By setting infolevel[IsHamiltonian] to an integer greater than 1 a message will be displayed stating how the graph was proven, or disproven, to be Hamiltonian.

An example of a graph which is Hamiltonian for which it will take exponential time to find a Hamiltonian cycle is the hypercube in d dimensions which has  vertices and  edges. The algorithm has no difficulty in finding a Hamiltonian cycle for  where  and  but for , , and  it takes a long time.

IsHamiltonian:   "graph satisfies MinimumDegree(G) >= NumberOfVertices(G)/2 ==> it is hamiltonian"

IsHamiltonian:   "graph satisfies IndependenceNumber(G) > NumberOfVertices(G)/2 ==> it's not hamiltonian"