Henson graph

To construct these graphs, Henson orders the vertices of the Rado graph into a sequence with the property that, for every finite set of vertices, there are infinitely many vertices having as their set of earlier neighbors. (Only the Rado graph has such a sequence.) He then defines to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every -clique of the Rado graph. With this construction, each graph is an induced subgraph of , and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph omits at least one vertex from each -clique of the Rado graph, there can be no -clique in . ==Universality==

Any finite or countable -clique-free graph can be found as an induced subgraph of by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in match the set of earlier neighbors of the corresponding vertex in . That is, is a universal graph for the family of -clique-free graphs. Because there exist -clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all -clique-free finite graphs as induced subgraphs. ==Symmetry==

Like the Rado graph, 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 when : for these graphs, every automorphism of the graph has more than one orbit. ==References==