On the probability that a random subgraph contains a circuit

Abstract

Let $\mu >2$ and $\epsilon >0$. We show that, if $G$ is a sufficiently large simple graph of average degree at least $\mu$, and $H$ is a random spanning subgraph of $G$ formed by including each edge independently with probability $p\ge \frac{1}{\mu -1}+\epsilon$, then $H$ contains a cycle with probability at least $1-\epsilon$.