# Are there more non-Hamiltonian graph than Hamiltonian on n vertices?

A Hamiltonian graph contains a Hamiltonian cycle. A non-Hamiltonian does not contain any Hamiltonian cycle. For every positive integer n are there more non-Hamiltonian graph than Hamiltonian on n vertices?

Maximum number of edges in a non-Hamiltonian graph

Maybe this could be useful

• I think you mean to say, "For every positive integer $n$ are there more ..." What are your thoughts on this? What have you done so far? – saulspatz Aug 30 '18 at 14:35
• – saulspatz Aug 30 '18 at 14:45
• Yes, it means that as $n$ goes to infinity, almost all the $n-$vertex graphs (labeled graphs, actually) are Hamiltonian. – saulspatz Aug 30 '18 at 15:46
• My last comment wasn't very good. When $p=\frac12,$ every labelled graph has the same probability of being chosen, so the probability that a labeled graph is Hamiltonian is equal to the fraction of labeled graphs that are Hamiltonian. – saulspatz Aug 30 '18 at 16:04
• @saulspatz Almost all random graphs have trivial automorphism group. (See, e.g., Theorem 3.1 in this paper, or earlier Theorem 2 in this paper.) So any w.h.p. result about $G(n,\frac12)$ extends to a result about almost all unlabeled graphs. – Misha Lavrov Aug 30 '18 at 18:25

OEIS A003216 gives the number of Hamiltonian graphs on $n$ points. No formula is given, but $a(8)=6196$ says there are $6196$ Hamiltonian graphs on $8$ points. OEIS A000088 gives the total number of graphs on $n$ unlabeled points. For $8$ points there are $12346$ so just over half the graphs on $8$ points are Hamiltonian. For $12$ points, the highest in the Hamiltonian list, there are $152522187830$ Hamiltonian graphs out of $165091172592$ which would claim that over $92\%$ of the $12$ point graphs are Hamiltonian.
For $n=2$ there are two graphs, neither of which is Hamiltonian. For $n \lt 8$ over half the graphs are not Hamiltonian. It doesn't seem surprising to me that once $n$ gets large most graphs are Hamiltonian. If you think about the complete graph on $n$ vertices you need very few of the edges to make a Hamiltonian path.