Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 144 / 2

The theory of the random graph has the extension property: for finite disjoint vertex sets $A,B$, there is a new vertex adjacent to every point of $A$ and to no point of $B$.

Let $M,N$ be countable models and let $f_0$ be a finite partial embedding. Enumerate $M=(m_i{)}_{i<\omega }$ and $N=(n_i{)}_{i<\omega }$. At an even stage, take the first $m_i$ outside the domain. Its adjacency pattern to the finite domain prescribes finite disjoint subsets of the range; the extension property in $N$ supplies a new image with exactly that pattern. At an odd stage, apply the same argument to the inverse map and the first unused $n_i$. This back-and-forth method produces an increasing sequence of finite partial embeddings whose union is an isomorphism. Hence every finite partial embedding extends to an isomorphism $M\cong N$.

Assume no induced graph on $P_i$ has the random-graph extension property. For each $i$, choose finite disjoint $A_i,B_i\subseteq P_i$ such that no vertex of $P_i\setminus (A_i\cup B_i)$ realizes the prescribed adjacency pattern. The unions $A={\bigcup }_i{A}_i$ and $B={\bigcup }_i{B}_i$ are finite and disjoint. The extension property in $M$ supplies a new vertex $v$ adjacent to all of $A$ and none of $B$. But $v\in P_j$ for some $j$, contradicting the choice of $A_j,B_j$. Thus some $P_j$ satisfies the extension property. It is a countable model of the theory of the random graph, so part (a) gives