Given a set of vertices $X$, a random graph is given by deciding, independently with probability $1/2$, whether each unordered pair of vertices should be joined by an edge or not. Following Peter Cameron’s book, Permutation Groups, we prove here that there exists a countable graph $R$ (unique up to isomorphism) such that each random countable graph is isomorphic to $R$ with probability $1$. Moreover, we shall see that the existence of such a graph implies a 0-1 law for first-order properties of finite graphs.

Definition: We say that a graph $\Gamma$ has the property $\mathcal{P}$ if for all disjoint finite subsets of vertices $U,V$ there exists a vertex $z \notin U \cup V$ joined to every vertex of $U$ and to no vertex of $V$.

The two following lemmas show that, up to isomorphism, there exists only one countable graph satisfying property $\mathcal{P}$: the so-called Rado graph, denoted $R$.

Lemma 1: Two countable graphs satisfying property $\mathcal{P}$ are isomorphic.

Proof. Let $\Gamma_1, \Gamma_2$ be two countable graphs satisfying property $\mathcal{P}$. For convenience, let $(f_1,f_2, \dots)$ and $(g_1,g_2, \dots)$ be an enumeration of $\Gamma_1$ and $\Gamma_2$ respectively.

Let $\varphi_0 : \emptyset \to \Gamma_2$ be the empty morphism. Then, by induction:

1) If $n$ is odd: Let $f$ be the first vertex in the enumeration of $\Gamma_1$ not in the domain $S_{n-1}$ of $\varphi_{n-1}$. If $U$ (resp. $V$) denotes the set of vertices of $S_{n-1}$ joined (resp. not joined) to $f$ by an edge, according to property $\mathcal{P}$, there exists a vertex $z \notin \varphi_{n-1}(U) \cup \varphi_{n-1}(V) = \varphi_{n-1}(S_{n-1})$ joined by an edge to any vertex of $\varphi_{n-1}(U)$ and to no vertex of $\varphi_{n-1}(V)$. Therefore, $\varphi_{n-1}$ can be extended to $\varphi_n : S_{n-1} \cup \{f\} \to \Gamma_2$ by setting $\varphi_n(f)=z$.

2) If $n$ is even: Let $g$ be the first vertex in the enumeration of $\Gamma_2$ not in the range $R_{n-1}$ of $\varphi_{n-1}$. If $U$ (resp. $V$) denotes the set of vertices of $R_{n-1}$ joined (resp. not joined) to $g$ by an edge, according to property $\mathcal{P}$, there exists a vertex $z \notin \varphi_{n-1}^{-1}(V) \cup \varphi_{n-1}^{-1}(U)= \varphi_{n-1}^{-1}(R_{n-1})$ joined by an edge to any vertex of $\varphi_{n-1}^{-1}(U)$ and to no vertex of $\varphi_{n-1}^{-1}(V)$. Therefore, $\varphi_{n-1}$ can be extended to $\varphi_n : S_{n-1} \cup \{z\} \to R_{n-1} \cup \{g \}$ by setting $\varphi_n(z)=g$.

Finally, $\varphi := \bigcup\limits_{n \geq 0} \varphi_n$ defines an isomorphism between $\Gamma_1$ and $\Gamma_2$. $\square$

It is worth noticing that the previous proof gives an isomorphism as soon as $\varphi_0$ is an isomorphism between two subgraphs. Therefore, we have:

Property 1: $R$ is homogenous, ie. every isomorphism between two finite induced subgraphs can be extented to an automorphism of $R$.

Moreover, using only the first step of our induction, we have:

Property 2: $R$ is universal, ie. every at most countable graph is isomorphic to a subgraph of $R$.

In fact, it can be shown that $R$ is the only countable, universal and homogenous graph (up to isomorphism); see Peter Cameron’s book for more details.

Lemma 2: A countable random graph has property $\mathcal{P}$ with probability $1$.

Proof. Because there exist only countably many pairs of finite subsets of vertices $(U,V)$, it is sufficient to show that the event that the property $\mathcal{P}$ for $U$ and $V$ fixed fails has probability $p$ zero. But the probability that a point $z \notin U \cup V$ be joined by an edge to any vertex of $U$ and to no vertex of $V$ is $1/2^k$, where $k= |U \cup V|$. Therefore,

$\displaystyle p = \lim\limits_{n \to + \infty} \left( 1- \frac{1}{2^k} \right)^n =0$. $\square$

In particular, lemma 2 shows that there exists a countable graph satisfying property $\mathcal{P}$, justifying our definition of $R$. We deduce the following theorem from lemmas 1 and 2:

Theorem 1: A countable random graph is isomorphic to $R$ with probability $1$.

From now on, let us consider graph theory from model theory viewpoint, that is we view a graph as a model of the theory

$\mathcal{T}_{\text{graph}} = \left\{ \forall x, \neg (x \sim x) ; \forall x,y (x \sim y \Leftrightarrow y \sim x) \right\}$

over the langage $\mathcal{L}= \{ \sim, =\}$. Here, the relation $x \sim y$ means that the vertices $x$ and $y$ are joined by an edge; therefore, in $\mathcal{T}_{\text{graph}}$ the graphs are unoriented and do not contain loops. It is worth noticing that a graph satisfies property $\mathcal{P}$ if and only if it satisfies the first-order sentence

$\Phi_{m,n} = \forall x_1, \dots, x_m \forall y_1, \dots, y_n \exists z \Phi_{m,n} ( \overline{x} , \overline{y},z)$

for all $m,n \geq 1$, where

$\Phi_{mn} (\overline{x}, \overline{y},z) = \left[ \bigwedge\limits_{i,n} (x_i \neq y_j ) \Rightarrow \left( \bigwedge\limits_{i,j} (z \neq x_i,y_j ) \wedge \bigwedge\limits_i (z \sim x_i ) \wedge \bigwedge\limits_{j} \neg (z \sim y_j) \right) \right]$.

Therefore, $\mathcal{P}$ is a first-order property. We now are able to deduce a 0-1 law for finite graphs:

Definition: A property is true in almost all finite graphs if the proportion of graphs of cardinality $n$ satisfying the given property tends to $1$ as $n \to + \infty$.

Theorem 2: Let $\sigma$ be a sentence in the first-order langage of graph theory. If $R \models \sigma$ (resp. if $R \not\models \sigma$) then $\sigma$ is true (resp. false) in almost all finite graphs. In particular, a first-ordre sentence is either true in almost all finite graphs or false in almost all finite graphs.

Proof. Suppose that $R \models \sigma$. By our previous remark, the sentence $\sigma$ can be logically deduced from the sentences $\Phi_{m,n}$, ie. $\{\Phi_{m,n}, m,n \geq 1 \} \vdash \sigma$. Then, it is a consequence of compactness theorem that $\sigma$ can be logically deduced from only finitely many sentences $\Phi_{m,n}$. Therefore, it is sufficient to prove that each $\Phi_{m,n}$ fails in a random graph of cardinality $k$ with probability $p_k$ such that $p_k \underset{k \to + \infty}{\longrightarrow} 0$.

Clearly, $p_k$ is smaller than the product of the number of choices of a subset of $m+n$ vertices by the probability that the other vertices are not correctly joined (so that $\Phi_{m,n}$ be not satisfied), that is

$\displaystyle p_k \leq C_{k}^{m+n} \left( 1- \frac{1}{2^{m+n}} \right)^{k-m-n} \underset{k \to + \infty}{\longrightarrow} 0$.

If $R \not\models \sigma$, then $R \models \neg \sigma$ and $\neg \sigma$ is true in almost all finite graphs. $\square$

It can be unsatisfactory that we only give a non-constructive proof for the existence of $R$; to conclude, we give an explicit construction:

Let $\mathbb{N}$ be the set of vertices; two integers $n < m$ are joined by an edge if and only if the $n$-th digit (from right to left) of $m$, written in binary, is one. Then, the constructed graph has property $\mathcal{P}$: Let $U, V$ be two finite disjoint subsets of vertices and $p \geq 1$ be such that $2^p>x$ for all $x \in U \cup V$. Now, let $z$ be the binary number $\epsilon_p \cdots \epsilon_0$, where $\epsilon_p=1$, and for every $0 \leq i \leq p-1$, $\epsilon_i=1$ if $i \in U$ and $0$ otherwise (in particular, if $i \in V$). Then $z \notin U \cup V$ is joined by an edge to every vertex of $U$ and to no vertex of $V$.