Oggi si riuniscono spesso vari modelli affini sotto il nome di «Erdős-Rényi»; il più naturale dal punto di vista probabilistico è certamente il seguente. Fissiamo un numero naturale n ≥ 1 e consideriamo l’insieme dei vertici { ①, ②, …, ⓝ}, in cui ogni coppia di vertici distinti forma un arco.
Vi sono dunque (n2)\binom{n }{2} archi possibili ((n2)\binom{n }{2} è naturalmente il consueto coefficiente binomiale, ossia il numero di modi di scegliere 2 oggetti fra n) e questi archi vengono aggiunti uno dopo l’altro in modo uniforme e casuale. Il procedimento genera una successione crescente di grafi aleatori (poiché gli archi sono aggiunti casualmente), indicati con
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)
dove G(n, m) è il grafo ottenuto dopo aver aggiunto m archi.
In particolare, G(n,0) è formato da n vertici isolati, mentre G(n,(n2))G\left( n,\binom{n }{2}\right) è il grafo completo; vedi la figura qui sotto.