# Hamiltonian paths in a simple graph

If a simple graph $$G$$ with $$n$$ vertices has a Hamiltonian cycle, what can we say about the number of Hamiltonian paths that $$G$$ has?

Since Hamiltonian cycle goes through each vertex only once the degree of each vertex is $$2$$, therefore, we can have $$n$$ Hamiltonian paths for a Hamiltonian cycle. For a number of Hamiltonian paths in $$G$$, it follows that there are total $$(n) \times (\text{no. of Hamiltonian cycle in}\ G$$) Hamiltonian paths in $$G$$.

Is my observation correct?

## 1 Answer

For each Hamiltonian cycle, we get $$n$$ Hamiltonian paths: a Hamiltonian cycle has $$n$$ edges, and if you delete any one of them you get a Hamiltonian path. That's $$2n$$ paths if you consider the reverse of a path different from the original.

Apart from this correction, you're right that $$M$$ Hamiltonian cycles produce $$n \cdot M$$ Hamiltonian paths, but there could be other Hamiltonian paths that don't arise in this way: any Hamiltonian path in which the first and last vertices aren't adjacent cannot come from a Hamiltonian cycle. So in general, you only get an inequality of the form you describe.

For example, consider knight's tours of an $$8 \times 8$$ chessboard. Here, any knight's tour is a Hamiltonian path, and any closed knight's tour is a Hamiltonian cycle. According to the OEIS, there are 13267364410532 Hamiltonian cycles and 19591828170979904 Hamiltonian paths: the second number is much bigger than $$128$$ times the first. (Here, we multiply by $$2n$$ to compare because the Hamiltonian paths OEIS is counting are directed.) Fewer than $$9\%$$ of the Hamiltonian paths come from Hamiltonian cycles.

• thanks for the example – thetraveller Nov 25 '18 at 22:54