Henson graph
# Henson graph

In graph theory, the Henson graph $G_i$ is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all $K_i-free$ finite graphs as induced subgraphs. For instance, $G_3$ 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. The first of these graphs, $G_3,$ is also called the homogeneous triangle-free graph or the universal triangle-free graph.

## Construction

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. (The existence of such a sequence uniquely defines the Rado graph.) He then defines $G_i$ 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.

With this construction, each graph $G_i$ is an induced subgraph of $G_{i+1},$ and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph $G_i$ omits at least one vertex from each i-clique of the Rado graph, there can be no i-clique in $G_i.$

## Universality

Any finite or countable i-clique-free graph H can be found as an induced subgraph of $G_i$ by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in $G_i$ match the set of earlier neighbors of the corresponding vertex in H. That is, $G_i$ is a universal graph for the family of i-clique-free graphs.

Because there exist i-clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph $G_i$ is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all i-clique-free finite graphs as induced subgraphs.

## Symmetry

Like the Rado graph, $G_3$ contains a bidirectional Hamiltonian path such that any symmetry of the path is a symmetry of the whole graph. However, this is not true for $G_i$ when i > 3: for these graphs, every automorphism of the graph has more than one orbit.

