# How many hamilton paths can a non-hamiltonian graph have?

What is the maximum number of hamilton paths a graph with $n$ vertices can have without having a hamiton cycle ?

If my turbo pascal program works well, the first few values for $3,4,...$ vertices are $2,4,12,48,240$ , which approves the conjecture that $2(n-2)!$ is the maximum.

• At least $(n-2)!$ – bof Aug 30 '14 at 22:41
• At least $2(n-2)!$, since it seems you are counting directed paths. Take the complete graph on $n-1$ vertices and adjoin one vertex $v$ by a single edge. All Hamilton paths must start or end with $v$ together with the single neighbour of $v$, but the remaining $n-2$ vertices can be visited in arbitrary order. – Erick Wong Aug 30 '14 at 23:12
• It seems that $2(n-2)!$ is indeed the maximum. If directed paths are not counted, the number would be $(n-2)!$ – Peter Aug 30 '14 at 23:30