Erdős–Rényi model

Builds on Graph Probability measure Binomial coefficient

Definition

Let $n \ge 1$ be an integer and let $\mathcal{G}_n$ be the set of all simple graphs with vertex set $[n] = \set{1, \ldots, n}$ . Let $N = \binom{n}{2}$ be the number of pairs of distinct vertices; see binomial coefficient.

For $0 \le p \le 1$ , the model $G(n, p)$ is the probability measure on $\mathcal{G}_n$ giving each graph with $m$ edges the probability $p^m (1 - p)^{N - m}$ .
For an integer $M$ with $0 \le M \le N$ , the model $G(n, M)$ is the uniform probability measure on the set of graphs in $\mathcal{G}_n$ with exactly $M$ edges.

Remarks

In $G(n, p)$ the $N$ events "the pair $\set{i, j}$ is an edge" are independent, each of probability $p$ . So the number of edges has the binomial distribution with parameters $N$ and $p$ , and its mean is $pN$ .

Example: for $n = 3$ and $p = 1/2$ , every graph on $\set{1, 2, 3}$ has probability $(1/2)^3 = 1/8$ , and these $8$ values sum to $1$ .

Non-example: on $\set{1, 2, 3}$ , choosing the triangle with probability $1/2$ and the empty graph with probability $1/2$ is not $G(3, p)$ for any $p$ . Its edge probability is $1/2$ , but the three edge events are not independent, since the graph with one edge has probability $0$ .

A random graph from these models is also written $G(n, p)$ or $G(n, M)$ . For $M$ near $pN$ the two models behave in a similar way.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`GJ4J77VV60`
URI	`m2://GJ4J77VV60`
Kind	definition
Writing	W0 stub
MSC	05C80, 60C05
Defines	Erdős–Rényi model
Uses	Graph, Probability measure, Binomial coefficient
Changed	2 November 2026

Erdős–Rényi model

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here