Minimum degree of an extremal forbidden-subgraph graph

ID: minimum-degree-of-an-extremal-forbidden-subgraph-graph

If a fixed graph has chromatic number , every extremal -free graph on vertices has minimum degree of a graph . Use a high-minimum-degree multipartite stability subgraph : replacing any vertex by one adjacent to all but one class of preserves -freeness. Any supposed new copy of can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.

New to topics? Read the docs here!