---
tag: GJ4J77VV60
kind: definition
name: Erdős–Rényi model
msc: [05C80, 60C05]
defines: 6E83YKANV3
uses: [00C0BR7D7H, 059TJN0NZ1, 0GBZM0MT0F]
sources:
  - url: https://en.wikipedia.org/wiki/Erdős–Rényi_model
---

## Definition

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

1. For $0 \le p \le 1$, the model $G(n, p)$ is the [[probability measure|059TJN0NZ1]] on $\mathcal{G}_n$ giving each graph with $m$ edges the probability $p^m (1 - p)^{N - m}$.
2. 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.