Hoy en día, varios modelos afines suelen agruparse bajo la denominación «Erdős-Rényi», y el más natural desde el punto de vista probabilístico es sin duda el siguiente. Fijemos un número natural n ≥ 1 y consideremos el conjunto de vértices { ①, ②, …, ⓝ}, en el que cada par de vértices distintos forma una arista.
Hay, por tanto, (n2)\binom{n }{2} aristas posibles ((n2)\binom{n }{2} es, por supuesto, el coeficiente binomial habitual, es decir, el número de maneras de elegir 2 objetos entre n) y estas aristas se añaden una tras otra al azar. Este procedimiento genera una sucesión creciente de grafos aleatorios (pues las aristas se añaden al azar), que se denotan
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)
donde G(n, m) es el grafo obtenido tras añadir m aristas.
En particular, G(n,0) está formado por n vértices aislados, mientras que G(n,(n2))G\left( n,\binom{n }{2}\right) es el grafo completo; véase la figura siguiente.