Extremal Graph Theory

Extremal graph theory is a branch of the mathematical field of graph theory. Extremal graph theory studies extremal (maximal or minimal) graphs which satisfy a certain property. Extremality can be taken with respect to different graph invariants, such as order, size or girth. More abstractly, it studies how global properties of a graph influence local substructures of the graph.

For example, a simple extremal graph theory question is "which acyclic graphs on n vertices have the maximum number of edges?" The extremal graphs for this question are trees on n vertices, which have n − 1 edges. More generally, a typical question is the following. Given a graph property P, an invariant u, and a set of graphs H, we wish to find the minimum value of m such that every graph in H which has u larger than m possess property P. In the example above, H was the set of n-vertex graphs, P was the property of being cyclic, and u was the number of edges in the graph. Thus every graph on n vertices with more than n − 1 edges must contain a cycle.

Several foundational results in extremal graph theory are questions of the above-mentioned form. For instance, the question of how many edges can an n-vertex graph have before it must contain as subgraph a clique of size k is answered by Turán's theorem. Instead of cliques, if the same question is asked for complete multi-partite graphs, the answer is given by the Erdős–Stone theorem.