find Hamiltonian cycle
find Hamiltonian path
(optional) zero or more options as specified below
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 circuit 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.
A 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 circuit contains a Hamiltonian path, but the reverse is not true.
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.
C ≔ CycleGraph⁡5
C≔Graph 1: an undirected unweighted graph with 5 vertices and 5 edge(s)
The Petersen graph is not Hamiltonian (that is, it does not contain a Hamiltonian circuit), but it does contain a Hamiltonian path.
P ≔ PetersenGraph⁡
P≔Graph 2: an undirected unweighted graph with 10 vertices and 15 edge(s)
The Petersen graph has a Hamiltonian path starting at 8 and ending at 4.
The Petersen graph does not have a Hamiltonian path starting at 8 and ending at 9.
The GraphTheory[FindHamiltonianCycle] and GraphTheory[FindHamiltonianPath] commands were introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
Download Help Document
What kind of issue would you like to report? (Optional)