Nowadays several closely related models are often grouped together under the name "Erdős-Rényi," and the most natural one from a probabilistic point of view is certainly the following one. Fix a natural number n ≥ 1 and consider the vertex set { ①, ②, …, ⓝ} in which every pair of distinct vertices forms an edge.
There are therefore (n2)\binom{n }{2} possible edges ( (n2)\binom{n }{2} is of course the usual binomial coefficient, that is, the number of ways to choose 2 objects among n) and these edges are added one after another uniformly at random. This process generates an increasing sequence of random graphs (since edges are added at random) denoted
G(n,0)⊂G(n,1)⊂...⊂G(n,m)⊂...⊂G(n,(n2))G(n,0) \subset G(n,1) \subset ... \subset G(n,m) \subset ... \subset G\left( n, \binom{n }{2}\right)
where G(n, m) is the graph obtained after adding m edges.
In particular, G(n,0) consists of n isolated vertices, whereas G(n,(n2))G\left( n,\binom{n }{2}\right) is the complete graph — see the figure below.