Suppose we have some method $M$ of generating sequences of letters from $\{p,q\}$ so that at each generation the probability of obtaining $p$ is $x$ , a real number strictly between $0$ and $1$ .

Let $\{a_{i}:i<\omega\}$ be a set of vertices. For each $i<\omega$ , $i\geq 1$ we construct a graph $G_{i}$ on the vertices $a_{1},\ldots,a_{i}$ recursively.

• $G_{1}$ is the unique graph on one vertex.
• For $i>1$ we must describe for any $j<k\leq i$ when $a_{j}$ and $a_{k}$ are joined.
  • If $k<i$ then join $a_{j}$ and $a_{k}$ in $G_{i}$ iff $a_{j}$ and $a_{k}$ are joined in $G_{i-1}$
  • If $k=i$ then generate a letter $l(j,k)$ with $M$ . Join $a_{j}$ to $a_{k}$ iff $l(j,k)=p$ .

Now let $\Gamma$ be the graph on $\{a_{i}:i<\omega\}$ so that for any $n,m <\omega$ , $a_{n}$ is joined to $a_{m}$ in $\Gamma$ iff it is in some $G_{i}$ .

Then we call $\Gamma$ a random graph. Consider the following property which we shall call f-saturation:

Given any finite disjoint $U$ and $V$ , subsets of $\{a_{i}:i<\omega\}$ there is some $a_{n} \in \{a_{i}:i<\omega\} \setminus (U \cup V)$ so that $a_{n}$ is joined to every point of $U$ and no points in $V$ .

Thus although the system of generation of a random graph looked as though it could deliver many potentially different graphs, this is not the case. Thus we talk about the random graph.

The random graph can also be constructed as a Fraisse limit of all finite graphs, and in many other ways. It is homogeneous and universal for the class of all countable graphs.

The theorem that almost every two infinite random graphs are isomorphic was first proved in [1].

Bibliography

1

Paul Erdos and Alfréd Rényi.
Asymmetric graphs.
Acta Math. Acad. Sci. Hung., 14:295-315, 1963.