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 an n-vertex graph can 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.
Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians.
Extremal graph theory started in 1941 when Turán proved his theorem determining those graphs of order n, not containing the complete graph Kk of order k, and extremal with respect to size (that is, with as many edges as possible). Another crucial year for the subject was 1975 when Szemerédi proved his result a vital tool in attacking extremal problems.
...
Wikipedia