0
$\begingroup$

In complete graph $K_n$, is it true that we can have at least $2*n$ Hamilton paths?

$\endgroup$
1
$\begingroup$

Since in a complete graph $K_n$ each two vertices are adjacent, the set of Hamiltonian paths of $K_n$ is exactly a set $S_n$ of permutations of its vertices. But $|S_n|=n!$, which is at least $2n$ when $n\ge 3$, but it is less than $2n$ for $n\le 2$.

$\endgroup$
  • $\begingroup$ I know it’s stupid, but you have to divide by two since the reverse of a permutation gives the same Hamiltonian path. $\endgroup$ – Bob Krueger Dec 19 '18 at 8:50
  • $\begingroup$ @BobKrueger I was aware of this point, so I have checked it (in “Chromatic Graph Theory” by Chartrand and Zhang). A path is defined as a sequence of vertices such that... . So, for instance, since the sequences $(1,2,3)$ and $(3,2,1)$ are distinct, these paths are distinct too. $\endgroup$ – Alex Ravsky Dec 21 '18 at 7:02
  • 1
    $\begingroup$ Fair enough. Then with that, the OP can prove their claim for any graph with a Hamiltonian cycle. $\endgroup$ – Bob Krueger Dec 21 '18 at 9:05

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.