<p>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$) (<a href="http://www.sciencedirect.com/science/article/pii/0012365X76900686">Pósa 1976</a>).  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.</p>

CC BY-SA 3.0
2014-11-06T11:10:10.550Z
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
CC BY-SA 3.0
2014-11-05T19:34:47.037Z
2014-11-05T19:34:47.037Z
mjqxxxx
<p>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?</p>

<hamiltonian-paths><phase-transition><random-graphs>
What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?
winston
# What's the probability for a random graph with degrees greater than 1 to be Hamiltonian?

(Asked by: username_0 on 2014-11-05)

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?

**Tags:** hamiltonian-paths, phase-transition, random-graphs


---

## 1 answers

### Answer by username_1 on 2014-11-05. Score: 6

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](http://www.sciencedirect.com/science/article/pii/0012365X76900686)). 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.

> **Comments:**
> **username_0**: 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.  

---

