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?
Best 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.