Homogeneous graph

A graph is defined to be k-ultrahomogeneous if every isomorphism between two of its induced subgraphs of at most k vertices can be extended to an automorphism of the whole graph.

If a graph is 5-ultrahomogeneous, then it is ultrahomogeneous for every k. The only finite connected graphs of this type are complete graphs, Turán graphs, 3 × 3 rook's graphs, and the 5-cycle.

There are only two connected graphs that are 4-ultrahomogeneous but not 5-ultrahomogeneous: the Schläfli graph and its complement. The proof relies on the classification of finite simple groups.

The infinite Rado graph is countably ultrahomogeneous.

See also

• Schläfli graph
• Rado graph