Given a set of vertices , a random graph is given by deciding, independently with probability , 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 (unique up to isomorphism) such that each random countable graph is isomorphic to with probability . 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 has the property if for all disjoint finite subsets of vertices there exists a vertex joined to every vertex of and to no vertex of .

The two following lemmas show that, up to isomorphism, there exists only one countable graph satisfying property : the so-called Rado graph, denoted .

**Lemma 1:** Two countable graphs satisfying property are isomorphic.

**Proof.** Let be two countable graphs satisfying property . For convenience, let and be an enumeration of and respectively.

Let be the empty morphism. Then, by induction:

1) If is odd: Let be the first vertex in the enumeration of not in the domain of . If (resp. ) denotes the set of vertices of joined (resp. not joined) to by an edge, according to property , there exists a vertex joined by an edge to any vertex of and to no vertex of . Therefore, can be extended to by setting .

2) If is even: Let be the first vertex in the enumeration of not in the range of . If (resp. ) denotes the set of vertices of joined (resp. not joined) to by an edge, according to property , there exists a vertex joined by an edge to any vertex of and to no vertex of . Therefore, can be extended to by setting .

Finally, defines an isomorphism between and .

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

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

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

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

In fact, it can be shown that 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 with probability .

**Proof.** Because there exist only countably many pairs of finite subsets of vertices , it is sufficient to show that the event that the property for and fixed fails has probability zero. But the probability that a point be joined by an edge to any vertex of and to no vertex of is , where . Therefore,

.

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

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

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

over the langage . Here, the relation means that the vertices and are joined by an edge; therefore, in the graphs are unoriented and do not contain loops. It is worth noticing that a graph satisfies property if and only if it satisfies the first-order sentence

for all , where

.

Therefore, 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 satisfying the given property tends to as .

**Theorem 2:** Let be a sentence in the first-order langage of graph theory. If (resp. if ) then 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 . By our previous remark, the sentence can be logically deduced from the sentences , ie. . Then, it is a consequence of compactness theorem that can be logically deduced from only finitely many sentences . Therefore, it is sufficient to prove that each fails in a random graph of cardinality with probability such that .

Clearly, is smaller than the product of the number of choices of a subset of vertices by the probability that the other vertices are not correctly joined (so that be not satisfied), that is

.

If , then and is true in almost all finite graphs.

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

Let be the set of vertices; two integers are joined by an edge if and only if the -th digit (from right to left) of , written in binary, is one. Then, the constructed graph has property : Let be two finite disjoint subsets of vertices and be such that for all . Now, let be the binary number , where , and for every , if and otherwise (in particular, if ). Then is joined by an edge to every vertex of and to no vertex of .