Henson graph
From Wikipedia, the free encyclopedia
In graph theory, the Henson graph Gi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs. For instance, G3 is a triangle-free graph that contains all finite triangle-free graphs.
These graphs are named after C. Ward Henson, who published a construction for them (for all i ≥ 3) in 1971.[1] The first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph.
To construct these graphs, Henson orders the vertices of the Rado graph into a sequence with the property that, for every finite set S of vertices, there are infinitely many vertices having S as their set of earlier neighbors. (Only the Rado graph has such a sequence.) He then defines Gi to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every i-clique of the Rado graph.[1]
With this construction, each graph Gi is an induced subgraph of Gi + 1, and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph Gi omits at least one vertex from each i-clique of the Rado graph, there can be no i-clique in Gi.