Universal graph

Summary

In mathematics, a universal graph is an infinite graph that contains every finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or random graph. More recent work has focused on universal graphs for a graph family $F$: that is, an infinite graph belonging to $F$ that contains all finite graphs in $F$. For instance, the Henson graphs are universal in this sense for the $i$-clique-free graphs.