# What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

Given a random graph by the Erdős–Rényi model, if the minimal node degree is greater than 1 (or $\geq 2$), or randomly select a graph from the graphs with node degrees greater than 1 ($\geq 2$), what's the probability for it to be a Hamiltonian graph?

The probability that a random graph with $n$ nodes and $cn\log n$ edges contains a Hamiltonian circuit tends to $1$ as $n\rightarrow\infty$ (and for sufficiently large $c$) (Pósa 1976). Since an ER random graph has $\Omega(n^2)$ edges, it is almost certainly Hamiltonian as $n\rightarrow \infty$, even without the constraint on the minimal degree.
• However, if the edge number of a random graph with $n$ nodes is ($n$/2)(log$n$ + log log$n$ + $c$), then the probability for it to be Hamiltonian is exp(-exp(-$c$)) (Komlos and Szemeredi 1983). So, it is interesting to know the Hamiltonian probability if the edge number of a random graph is less than $cn$log$n$ and the node degrees are greater than 1. – winston Nov 6 '14 at 11:10