# Hamilton Paths in Complete graph $K_n$

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

## 1 Answer

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$$.

• I know it’s stupid, but you have to divide by two since the reverse of a permutation gives the same Hamiltonian path. – Bob Krueger Dec 19 '18 at 8:50
• @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. – Alex Ravsky Dec 21 '18 at 7:02
• Fair enough. Then with that, the OP can prove their claim for any graph with a Hamiltonian cycle. – Bob Krueger Dec 21 '18 at 9:05