In mathematics, a k-ultrahomogeneous graph is a graph in which every isomorphism between two of its induced subgraphs of at most k vertices can be extended to an automorphism of the whole graph.
A k-homogeneous graph obeys a weakened version of the same property in which every isomorphism between two induced subgraphs implies the existence of an automorphism of the whole graph that maps one subgraph to the other (but does not necessarily extend the given isomorphism).
[1] A homogeneous graph is a graph that is k-homogeneous for every k, or equivalently k-ultrahomogeneous for every k.[1] It is a special case of a homogenous model.
The proof relies on the classification of finite simple groups.
[4] A graph is connected-homogeneous if every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.