The theory of the random graph is the theory of a set {\displaystyle V} (thought of as vertices) and a binary relationship {\displaystyle R} on {\displaystyle V} (thought of as indicating the existence of an edge between two vertices), such that {\displaystyle R} is irreflexive and symmetric, and such that the following condition holds: if {\displaystyle X} and {\displaystyle Y} are finite subsets of {\displaystyle V}, with {\displaystyle X\cap Y=\emptyset }, then there is a {\displaystyle v\in V} such that {\displaystyle vRx} holds for {\displaystyle x\in X}, and {\displaystyle vRy} fails for {\displaystyle y\in Y}. That is, {\displaystyle v} is connected to everyone in {\displaystyle X}, and not connected to anyone in {\displaystyle Y}. Without this last condition, we would just have the theory of graphs. The theory of the random graph is the model companion of the theory of graphs.

The theory of the random graph is countably categorical, and simple, but not NIP (and hence not stable). It has quantifier elimination. It does not have elimination of imaginaries.

The term "random graph" refers (maybe?) to the following fact: if we declare our vertex set to be {\displaystyle \mathbb {N} } (or any countable set), and we choose for each pair of distinct vertices {\displaystyle v_{1}\neq v_{2}} whether there will be an edge from {\displaystyle v_{1}} to {\displaystyle v_{2}}, with probability {\displaystyle 1/2}, independently between different pairs, then the resulting graph will be a random graph with probability 1. ::: ::: :::