# Are “almost all” graphs hamiltonian?

Let $$p(n):=\frac{\text{number of hamiltonian graphs with n nodes}}{\text{number of graphs with n nodes}}$$

Since $883156024$ of the $1018997864$ graphs with $11$ nodes are hamiltonian, we have $p(11) = 0.8667$. Is it known whether $$\lim_{n\to\infty} p(n) = 1$$

and if yes, is it known how fast this convergence is ?

• Perhaps, it helps, that "almost all" graphs are $2$-connected. – Peter Oct 21 '14 at 20:08

The following stronger result is known. Assume that the edges of the graph $G$ with $n$ vertices are drawn in mutually independently with probability $\frac{c\ln n}{n}$. Then, for a sufficiently large $c$, the probability that $G$ contains a Hamiltonian circuit tends to $1$ as $n \to \infty$. This is Theorem 2 from this old paper by Pósa, available online for free.
• I do not see why this result is stronger, but since it is plausible that "allmost all" graphs have $O(n\ ln\ n)$ edges, it should answer my question. – Peter Oct 21 '14 at 20:41
• Note that there are about $\frac 12n^2$ potential edges in a graph with $n$ nodes. Since most graphs have of order half the available edges, we would expect most graphs to have more than $c\frac 14n^2 \gt n \ln n$ edges for any $0 \lt c \lt 1$ once $n$ gets large enough. – Ross Millikan Oct 21 '14 at 20:43