The Rado graph, also called the countable random graph, is the unique countably infinite simple graph, up to graph
isomorphism, with the following property. For any two disjoint finite sets 
and 
of vertices, there is a graph
vertex 
outside 
that is adjacent to every graph vertex in 
and to no graph vertex in
(Rado 1964, Cameron 1997, 2001; Bondy
and Murty 2008, p. 341).
A random graph on a countably infinite set of vertices, formed by independently including each possible graph edge with probability 1/2, has this property with probability one. Consequently, it is isomorphic to the Rado graph with probability one (Cameron 1997, 2001; Bondy and Murty 2008, p. 341). This infinite graph is distinct from any individual finite realization of a random graph.
This property also implies that every finite graph occurs as an induced subgraph of the Rado graph. Its vertices can be chosen successively, prescribing adjacency and nonadjacency to all previously chosen vertices at each step.
