Rado graph

Description

The Rado graph $R$ has vertex set $\N = \set{0, 1, 2, \dots}$. For $i < j$, the vertices $i$ and $j$ are adjacent when the binary digit of $j$ at position $i$ is $1$. Equivalently, $\floor{j / 2^i}$ is odd.

It has the extension property, stated as follows. For any two disjoint finite sets $U, V \subseteq \N$, some vertex $z \notin U \cup V$ is adjacent to every vertex of $U$ and to no vertex of $V$. Check: let $N$ be larger than every element of $U \cup V$ and put $z = 2^N + \sum_{u \in U} 2^u$. Then $z > N$, so $z \notin U \cup V$, and every $w \in U \cup V$ satisfies $w < z$. The binary digit of $z$ at position $w$ is $1$ if $w \in U$ and $0$ if $w \in V$. So $z$ is adjacent to every vertex of $U$ and to no vertex of $V$.