# Least graph with exactly $2014$ hamiltonian circuits?

• What is the least graph with exactly $2014$ hamiltonian circuits ?

First of all, I am not sure, if for every natural number $n$, there is a graph with exactly $n$ hamiltonian circuits. Is that so, and if yes, how can it be proven ? If no, for which numbers does no graph exist ?

I used an online graph theory program to check the graphs with $9$ nodes or less. I found $3$ graphs with $9$ nodes and $2016$ hamiltonian circuits, but none with $2012-2015$ hamiltonian circuits. The cubic graphs upto $18$ vertices have less then $2000$ hamiltonian circuits.

• $18$ graphs with $9$ nodes have exactly $2014$ hamiltonian paths. – Peter Oct 16 '14 at 21:48

This is an answer for question in the title. I claim that the least such graph has $10$ nodes (assuming the data from the comment, stating that there is a graph with $9$ nodes which has exactly $2014$ hamiltonian paths).
If there is a graph $G$ on $v$ vertices with $N$ Hamiltonian paths, we can add a new vertex and connect it with all vertices from $G$. This will produce a graph on $v+1$ vertices with $N$ Hamiltonian circuits. So, in particular, there is a graph on $10$ vertices with exactly $2014$ Hamiltonian circuits. This graph is minimal because, as it is mentioned in the question, no graph with $9$ nodes or less satisfies this property.
Since the cycle of length $h$ has exactly $h$ Hamiltonian paths, these considerations answer the second question as well.
• Very nice! So, the additional question can be reduced to the problem of finding graphs with $n$ hamiltonian paths. – Peter Oct 16 '14 at 22:15
• Yes. And we can note that $n$-cycles satisfy this property (as to the second question). – user2097 Oct 16 '14 at 22:18