# Number of Hamiltonian cycles on random graphs

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)$?

• You can probably answer Q1 yourself. Hint: Linearity of expectation. – Yuval Filmus Oct 8 '12 at 13:15

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.