1 | initial version |

Hi,

Sage has the command:

```
hamiltonian_cycle(algorithm='tsp')
```

"Returns a Hamiltonian cycle/circuit of the current graph/digraph A graph (resp. digraph) is said to be Hamiltonian if it contains as a subgraph a cycle (resp. a circuit) going through all the >vertices. Computing a Hamiltonian cycle/circuit being NP-Complete, this algorithm could run for some time depending on the instance.

ALGORITHM:

See Graph.traveling_salesman_problem for ‘tsp’ algorithm and find_hamiltonian from sage.graphs.generic_graph_pyx for >>‘backtrack’ algorithm.

INPUT:

algorithm - one of ‘tsp’ or ‘backtrack’. OUTPUT: If using the ‘tsp’ algorithm, returns a Hamiltonian cycle/circuit if it exists; otherwise, raises a EmptySetError exception. If >>using the ‘backtrack’ algorithm, returns a pair (B,P). If B is True then P is a Hamiltonian cycle and if B is False, P is a >>longest path found by the algorithm. Observe that if B is False, the graph may still be Hamiltonian. The ‘backtrack’ >>algorithm is only implemented for undirected graphs."

The above is directly from Hamiltonian Cycle

Added in the same area on the page is:

```
sage: g = graphs.HeawoodGraph()
sage: g.hamiltonian_cycle()
TSP from Heawood graph: Graph on 14 vertices
sage: g = graphs.PetersenGraph()
sage: g.hamiltonian_cycle()
Traceback (most recent call last):
...
EmptySetError: The given graph is not Hamiltonian
```

So clearly there is some algorithms on your question, though it is also known that this is an NP-Complete problem.

Good luck, fieldofnodes

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.