I'd like to compute the number of edges necessary to build all Hamiltonian paths in a complete digraph.
My thoughts so far:

Let $N$ be the number of nodes.

  • number of Hamiltonian paths: $N!$
  • number of edges per path: $N-1$
  • total number of edges necessary to build all paths: $N!*(N-1)$ (assuming an edge gets consumed when building a path)

I have a given solution: $N!*N$
Can someone explain where the extra factor of N comes in?

  • $\begingroup$ Does the complete digraph have a specific orientation? or does it have double edges? $\endgroup$ – Jorge Fernández Hidalgo Jan 31 '16 at 21:24
  • $\begingroup$ @dREaM im not sure what you mean (my knowledge in graphs is very limited). There are two edges between every two nodes one from "A" to "B" and one of opposite directionality $\endgroup$ – Dahlai Jan 31 '16 at 22:06

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.