Random Graph

The canonical random graph model, the Erdős–Rényi model, introduced by Paul Erdős and Alfréd Rényi in 1959 and independently by Edgar Gilbert, is denoted G(n, p): a graph on n vertices where each possible edge appears independently with probability p. Despite its simplicity, G(n, p) exhibits phenomena that are neither simple nor obvious.