method=one of legacy, sat, or tsp.

Specifies the algorithm to use in seeking a Hamiltionian circuit. The default, method=legacy, uses a simple depth-first search to find a Hamiltonian circuit. The sat method encodes the problem as a logical formula and seeks a satisfying solution, and the tsp method seeks to find a Hamiltonian circuit which is an optimal solution to the traveling salesman problem.

A graph G on n vertices is Hamiltonian if there exists a Hamiltonian circuit, that is, a cycle in G containing each of the n vertices exactly 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 $\left[1\,2\,3\,1\right]$.

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 $\frac{n}{2}$ where $n$ 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 $\frac{n}{2}$. If so, then G is not Hamiltonian.  Failing these checks, the default 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 $n=2^d$ vertices and $m=d{2}^{d-1}$ edges. The algorithm has no difficulty in finding a Hamiltonian cycle for $d=5$ where $n=32$ and $m=80$ but for $d=6$, $n=64$, and $m=192$ it takes a long time.

The following are graphs in the SpecialGraphs subpackage which are Hamiltonian..

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{with}\left(\mathrm{SpecialGraphs}\right)\:$

$P≔\mathrm{PetersenGraph}\left(\right)$

$P≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 15\; edge(s)}$

$\mathrm{IsHamiltonian}\left(P\right)$

$\mathrm{false}$

$\mathrm{AddEdge}\left(P\,\left\{1\,3\right\}\right)$

$\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 10\; vertices\; and\; 16\; edge(s)}$

$\mathrm{IsHamiltonian}\left(P\,'C'\right)$

$\mathrm{true}$

$C$

$\left[1\,2\,9\,8\,5\,4\,10\,6\,7\,3\,1\right]$

$\mathrm{DrawGraph}\left(P\right)$

$\mathrm{H3}≔\mathrm{HypercubeGraph}\left(3\right)$

$\mathrm{H3}≔\mathrm{Graph\; 2:\; an\; undirected\; graph\; with\; 8\; vertices\; and\; 12\; edge(s)}$

$\mathrm{IsHamiltonian}\left(\mathrm{H3}\,'C'\right)$

$\mathrm{true}$

$C$

$\left[''000''\,''100''\,''110''\,''010''\,''011''\,''111''\,''101''\,''001''\,''000''\right]$

$\mathrm{HighlightTrail}\left(\mathrm{H3}\,C\,\mathrm{red}\right)$

$\mathrm{DrawGraph}\left(\mathrm{H3}\right)$

$\mathrm{infolevel}\left[\mathrm{IsHamiltonian}\right]≔2$

${\mathrm{infolevel}}_{\mathrm{IsHamiltonian}}≔2$

$\mathrm{IsHamiltonian}\left(\mathrm{H3}\right)$

$\mathrm{true}$

$\mathrm{K33}≔\mathrm{CompleteGraph}\left(3\,3\right)$

$\mathrm{K33}≔\mathrm{Graph\; 3:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 9\; edge(s)}$

$\mathrm{IsHamiltonian}\left(\mathrm{K33}\right)$

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

$\mathrm{true}$

$\mathrm{K34}≔\mathrm{CompleteGraph}\left(3\,4\right)$

$\mathrm{K34}≔\mathrm{Graph\; 4:\; an\; undirected\; graph\; with\; 7\; vertices\; and\; 12\; edge(s)}$

$\mathrm{IsHamiltonian}\left(\mathrm{K34}\right)$

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

$\mathrm{false}$

The GraphTheory[IsHamiltonian] command was updated in Maple 2019.

The method option was introduced in Maple 2019.

For more information on Maple 2019 changes, see Updates in Maple 2019.