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.

  • 4
    $\begingroup$ At least $(n-2)!$ $\endgroup$ – bof Aug 30 '14 at 22:41
  • 6
    $\begingroup$ 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. $\endgroup$ – Erick Wong Aug 30 '14 at 23:12
  • $\begingroup$ It seems that $2(n-2)!$ is indeed the maximum. If directed paths are not counted, the number would be $(n-2)!$ $\endgroup$ – Peter Aug 30 '14 at 23:30

Your Answer

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

Browse other questions tagged or ask your own question.