= Solution
The theory RG says that the edge relation is irreflexive and symmetric and includes, for every $m,n$, the extension axiom asserting that for disjoint vertices $u_1,\ldots,u_m,v_1,\ldots,v_n$ there is a new vertex adjacent to every $u_i$ and no $v_j$. Every finite subset of these axioms has a finite model by choosing a sufficiently large random graph, so compactness proves consistency. Equivalently, the countable Rado graph is an explicit model.
Any finite partial graph isomorphism extends by one vertex using the extension axiom. Back-and-forth therefore makes every partial embedding elementary, proving <quantifier elimination for the random graph>.
By quantifier elimination, a three-type is determined by equality and adjacency. There is one type with all variables equal. If exactly two are equal, there are three choices of the equal pair and two choices for adjacency to the third vertex, giving six. If all are distinct, the three possible edges can be chosen independently, giving eight. Thus the <three-type space of the random graph> has
$$
1+6+8=15
$$
elements, with the discrete Stone topology.
Back to article page
