startvertex=a valid vertex in G

Specifies the starting vertex for a Hamiltonian cycle or path. If provided, the algorithm will only consider cycles or paths beginning at startvertex.

endvertex=a valid vertex in G

Specifies the ending vertex for a Hamiltonian path. If provided, the algorithm will only consider paths terminating at endvertex.

The FindHamiltonianCycle(G) function returns a Hamiltonian cycle as a list of vertices of G if such a path exists in G, and NULL otherwise.

The FindHamiltonianPath(G) function returns a Hamiltonian path as a list of vertices of G if such a path exists in G, and NULL otherwise.

Optional starting and ending vertices may be specified with the startvertex and endvertex options, respectively. Note that endvertex is valid only for FindHamiltonianPath.

The algorithm works for both undirected and directed graphs and ignores edge weights for weighted graphs.

Note that the TravelingSalesman command also returns a Hamiltonian cycle, specifically the least-weight Hamiltonian cycle. By contrast FindHamiltonianCycle returns the first Hamiltonian cycle it can find, if one exists, and does not attempt to find a cycle of least weight.

A Hamiltonian cycle (also called Hamiltonian circuit) for a graph G on n vertices is a cycle in G containing each of the n vertices exactly once.

A Hamiltonian path for a graph G on n vertices is a path of length n which visits each vertex of G exactly once. Note that every Hamiltonian cycle contains a Hamiltonian path, but the reverse is not true.

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

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

$C≔\mathrm{CycleGraph}\left(5\right)$

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

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

$\mathrm{true}$

$\mathrm{FindHamiltonianCycle}\left(C\right)$

$\left[1\,2\,3\,4\,5\,1\right]$

$\mathrm{FindHamiltonianCycle}\left(C\,\mathrm{startvertex}=4\right)$

$\left[4\,3\,2\,1\,5\,4\right]$

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

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

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

$\mathrm{false}$

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

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

$\mathrm{FindHamiltonianPath}\left(P\,\mathrm{startvertex}=8\,\mathrm{endvertex}=4\right)$

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

$\mathrm{FindHamiltonianPath}\left(P\,\mathrm{startvertex}=8\,\mathrm{endvertex}=9\right)$

The GraphTheory[FindHamiltonianCycle] and GraphTheory[FindHamiltonianPath] commands were introduced in Maple 2019.

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