On the Probability that a Random Subgraph Contains a Circuit
On the Probability that a Random Subgraph Contains a Circuit
Let and . We show that, if G is a sufficiently large simple graph of average degree at least μ, and H is a random spanning subgraph of G formed by including each edge independently with probability , then H contains a cycle with probability at least .