Random Graph — Definition, Formula & Examples

A random graph is a graph constructed by some random process, most commonly by including each possible edge independently with a fixed probability. It is the central object of study in probabilistic combinatorics.

In the Erdős–Rényi model $G(n, p)$ , a random graph on $n$ labeled vertices is formed by independently including each of the $\binom{n}{2}$ possible edges with probability $p \in [0, 1]$ . An alternative model $G(n, m)$ selects a graph uniformly at random from all graphs on $n$ vertices with exactly $m$ edges.

Key Formula

\mathbb{E}[|E|] = \binom{n}{2} p = \frac{n(n-1)}{2}\, p

Where:

$n$ = Number of vertices in the graph
$p$ = Probability that any given edge is included
$|E|$ = Number of edges in the random graph

How It Works

In the

G(n, p)

model, you start with

n

isolated vertices. For every pair of distinct vertices, you flip a biased coin with probability

p

of heads; if heads, you add that edge. The resulting graph is random — its number of edges, degree sequence, and connectivity all vary from one realization to the next. Many graph properties exhibit a threshold phenomenon: as

p

crosses a critical value (depending on

n

), the probability that the graph has that property jumps from near 0 to near 1. For instance, the threshold for the graph to become connected is

p = \frac{\ln n}{n}

Worked Example

Problem: In the Erdős–Rényi model G(6, 0.4), find the expected number of edges and the probability that a specific vertex has degree exactly 2.

Expected edges: The total number of possible edges is

\binom{6}{2} = 15

. Multiply by

p

\mathbb{E}[|E|] = 15 \times 0.4 = 6

Degree distribution: Each vertex can connect to 5 others. The degree of any vertex follows a Binomial(5, 0.4) distribution. Compute

P(\text{deg} = 2)

P(\text{deg}=2) = \binom{5}{2}(0.4)^2(0.6)^3 = 10 \times 0.16 \times 0.216 = 0.3456

Answer: The expected number of edges is 6, and the probability that a given vertex has degree exactly 2 is 0.3456.

Why It Matters

Random graphs underpin the analysis of real-world networks — from the internet's topology to social networks and epidemiological models. In theoretical computer science, the probabilistic method uses random graphs to prove the existence of graphs with extremal properties that are hard to construct explicitly.

Common Mistakes

Mistake: Confusing the two Erdős–Rényi models G(n, p) and G(n, m).

Correction: G(n, p) includes each edge independently with probability p, so the edge count is random. G(n, m) fixes the edge count at exactly m and chooses uniformly among all such graphs. Results often transfer between models, but the distinction matters for precise probability calculations.