<p>As Yuval said, Q1 is easy to answer using linearity of expectation (spoiler: $(n-1)!p^n$) . I don't know the exact answer to Q2, but it might be good enough if you know it's very low: for the range of $p$ where there is at least one cycle, it holds that $P[\text{there is more than one cycle} | \text{there is at least one cycle}]&gt;1-1/n^{\log n}$ or so. In other words, once there is one cycle, there are many. The reason is that once there is one cycle, there are around $n^2$ ways to create another cycle from it by exchanging two edges of the cycle by the two "crossing" edges (this is called a "2-flip" or something in some of the relevant literature). For any pair of edges, the chance you can do that is $p^2$. So for all of these to fail, the chance is $(1-p^2)^{n^2}$ which is roughly $e^{-(pn)^2}$, which is pretty tiny.</p>

CC BY-SA 3.0
2012-10-10T15:13:38.837Z
2012-10-11T01:59:44.157Z
2012-10-11T01:59:44.157Z
anonymous moose
<p>We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:</p>

<p>\begin{eqnarray}
Pr [G\mbox{  has a Hamiltonian cycle}]=
  \begin{cases}
    1 &amp; (c(n)\rightarrow \infty) \\
    0 &amp; (c(n)\rightarrow - \infty) \\
 e^{-e^{-c}} &amp; (c(n)\rightarrow c)
  \end{cases}
\end{eqnarray}</p>

<p>I want to know results about the number of Hamiltonian cycles on random graphs.</p>

<p>Q1. How many is the expected number of Hamiltonian cycles on $G(n,p)$?</p>

<p>Q2. What is the probability $Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$ for the edge probability $p$ on $G(n,p)$?</p>

CC BY-SA 3.0
2012-10-08T13:15:28.417Z
You can probably answer Q1 yourself. Hint: Linearity of expectation.
Yuval Filmus
<graph-theory><co.combinatorics><randomness>
Number of Hamiltonian cycles on random graphs
Elely
# Number of Hamiltonian cycles on random graphs

(Asked by: username_0 on 2012-10-08)

We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:

\begin{eqnarray}
Pr [G\mbox{ has a Hamiltonian cycle}]=
\begin{cases}
1 & (c(n)\rightarrow \infty) \\
0 & (c(n)\rightarrow - \infty) \\
e^{-e^{-c}} & (c(n)\rightarrow c)
\end{cases}
\end{eqnarray}

I want to know results about the number of Hamiltonian cycles on random graphs.

Q1. How many is the expected number of Hamiltonian cycles on $G(n,p)$?

Q2. What is the probability $Pr [G \textrm{ has a \*unique\* Hamiltonian cycle}]$ for the edge probability $p$ on $G(n,p)$?

**Tags:** graph-theory, co.combinatorics, randomness

> **Comments:**
> **username_1**: You can probably answer Q1 yourself. Hint: Linearity of expectation.  

---

## 1 answers

### Answer by username_2 on 2012-10-10. Score: 7 | Accepted answer

As Yuval said, Q1 is easy to answer using linearity of expectation (spoiler: $(n-1)!p^n$) . I don't know the exact answer to Q2, but it might be good enough if you know it's very low: for the range of $p$ where there is at least one cycle, it holds that $P[\text{there is more than one cycle} | \text{there is at least one cycle}]>1-1/n^{\log n}$ or so. In other words, once there is one cycle, there are many. The reason is that once there is one cycle, there are around $n^2$ ways to create another cycle from it by exchanging two edges of the cycle by the two "crossing" edges (this is called a "2-flip" or something in some of the relevant literature). For any pair of edges, the chance you can do that is $p^2$. So for all of these to fail, the chance is $(1-p^2)^{n^2}$ which is roughly $e^{-(pn)^2}$, which is pretty tiny.


---

