 Extremal graph theory

Extremal graph theory asks how large or dense a graph can be while avoiding a prescribed configuration. For a fixed graph $F$, its extremal number $\mathrm{ex}(n,F)$ is the maximum number of edges in an $n$-vertex simple graph containing no copy of $F$ as a subgraph.

For instance, Mantel theorem gives $\mathrm{ex}(n,K_3)=\lfloor n^2/4\rfloor$: a balanced complete bipartite graph has that many edges and no triangle. The Turan theorem generalizes this to forbidden cliques. Such bounds turn a numerical observation, having many edges, into a structural conclusion, the forced presence of a pattern.

Extremal graph theory is a branch of combinatorial mathematics that studies the extremal properties of graphs. Specifically, it focuses on questions related to the maximal or minimal number of edges in a graph that satisfies certain properties or conditions. The primary goal is often to determine the extremal (that is, maximum or minimum) values for specific parameters of graphs (like the number of edges, number of vertices, etc.) that meet certain constraints, such as containing a particular subgraph or avoiding certain configurations.