The **theory of the random graph** is the theory of a set $ V $ (thought of as vertices) and a binary relationship $ R $ on $ V $ (thought of as indicating the existence of an edge between two vertices), such that $ R $ is irreflexive and symmetric, and such that the following condition holds: if $ X $ and $ Y $ are finite subsets of $ V $, with $ X \cap Y = \emptyset $, then there is a $ v \in V $ such that $ vRx $ holds for $ x \in X $, and $ vRy $ fails for $ y \in Y $. That is, $ v $ is connected to everyone in $ X $, and not connected to anyone in $ 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 $ \mathbb{N} $ (or any countable set), and we choose for each pair of distinct vertices $ v_1 \ne v_2 $ whether there will be an edge from $ v_1 $ to $ v_2 $, with probability $ 1/2 $, independently between different pairs, then the resulting graph will be a random graph with probability 1.