Extremal graph theory
is a branch of mathematics
In the narrow sense, extremal graph theory studies the graphs which are extremal among graphs with a certain property. There are various meanings for the word extremal: with the largest number of edges, the largest minimum degree, the smallest diameter, etc. In a broader sense, various other related questions can be included into extremal graph theory. In that case, the term extremal graph theory can encompass a large part of graph theory.
A typical result in extremal graph theory is Turán's theorem. It answers the following question. What is the maximum possible number of edges in an undirected graph G with n vertices which does not contain K3 (three vertices A, B, C with edges AB, AC, BC; i.e. a triangle) as a subgraph? The bipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains
edges. Similar questions have been studied with various other subgraphs H
instead of K3
; for instance, the Zarankiewicz problem
concerns the largest graph that does not contain a fixed complete bipartite graph
as a subgraph. Turán
also found the (unique) largest graph not containing Kk
which is named after him, namely Turán graph
. This graph has
edges. For C4
, the largest graph on n
vertices not containing C4
- Béla Bollobás. Extremal Graph Theory. New York: Academic Press, 1978.
- Béla Bollobás. Modern Graph Theory, chapter 4: Extremal Problems. New York: Springer, 1998.
- M. Simonovits, Slides from the Chorin summer school lectures, 2006.