I am interested in a random graph $G\sim G(n,p)$. I know that if $p<<1/n$, then $G$ will be a forest. I happen to be interested in the boundary case where $p=c/n$, where $c<1$ is a constant. Does $G$ *fail* to be a forest with high probability in this case? Or is it still a forest some positive proportion of the time? Does it depend on $c$? References would be very appreciated as I don't know much about graph theory.



Threshold for appearance of a cycle
In this case, assuming $c\lt 1$ is independent of $n$, the number of cycles is asymptotically Poisson with constant mean $f(c)$. So asymptotically there is a constant nonzero probability $e^{-f(c)}$ that there are no cycles. With a rough calculation that needs checking, I got
$$ e^{-f(c)} = \sqrt{1-c}\,\exp\bigl({{\textstyle\frac14}c(2+c)}\bigr).$$
You can see that the probability of being a forest goes to 0 as $c$ approaches 1 from below. The formula is not valid at all for $c\gt 1$.


Calculation (apply the word "asymptotically" to everything): the expected number of $k$-cycles is $E(C\_k)=\frac1{2k}c^k$. The sum of $E(C\_k)$ over $k\in[3,\infty]$ is $f(c) = -\frac12\ln(1-c)-\frac12c-\frac14c^2$ and so $e^{-f(c)}$ is the above.


