go-v.orgcodex
Menu
Page tools

codex · Philosophy

Henson graph

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. The first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph.

Wikipedia contributors, "Henson graph", Wikipedia, revision 1280021819, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex