Erdős–Rényi model

Summary

The Erdős–Rényi model is the simplest model of a random graph. In the form $G(n, p)$, each of the $\binom{n}{2}$ possible edges on $n$ labelled vertices is present independently with probability $p$. In the form $G(n, M)$, a graph with exactly $M$ edges is chosen uniformly at random. The model shows sharp thresholds, such as the sudden appearance of a giant component, and it is a basic tool of the probabilistic method.