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?


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.

  • $\begingroup$ thanks for the example $\endgroup$ – thetraveller Nov 25 '18 at 22:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.