**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 *K*_{3} (three vertices *A*, *B*, *C* with edges *AB*, *AC*, *BC*) as a subgraph? This graph is known as a Turán graph, it contains edges. Similar questions has been studied with various other subgraphs *H* instead of *K*_{3}. Turán also found the largest graph not containing *K*_{k}. This graph has edges. For *C*_{4}, the largest graph on *n* vertices not containing *C*_{4} has edges.
## References - Bela Bollobas. Extremal Graph Theory. New York: Academic Press, 1978.
- Bela Bollobas. Modern Graph Theory. (Chapter 4: Extremal Problems.) New York: Springer, 1998.
- Eric W. Weisstein. Extremal Graph Theory. From MathWorld--A Wolfram Web Resource. [1] (
*http://mathworld.wolfram.com/ExtremalGraphTheory.html*) |