Editing Turán's theorem (section)

{{Short description|Extremal graph theory bound on clique-free graph edges}}
{{distinguish|text=[[Turán's method]] in analytic number theory}}
In [[graph theory]], '''Turán's theorem''' bounds the number of edges that can be included in an [[undirected graph]] that does not have a [[clique (graph theory)|complete subgraph]] of a given size. It is one of the central results of [[extremal graph theory]], an area studying the largest or smallest graphs with given properties, and is a special case of the [[forbidden subgraph problem]] on the maximum number of edges in a graph that does not have a given subgraph.

An example of an <math>n</math>-[[vertex (graph theory)|vertex]] graph that does not contain any <math>(r+1)</math>-vertex clique <math>K_{r+1}</math> may be formed by partitioning the set of <math>n</math> vertices into <math>r</math> parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the [[Turán graph]] <math>T(n,r)</math>. Turán's theorem states that the Turán graph has the largest number of edges among all {{math|''K''<sub>''r''+1</sub>}}-free {{mvar|n}}-vertex graphs.

Turán's theorem, and the [[Turán graph]]s giving its extreme case, were first described and studied by [[Hungary|Hungarian]] mathematician [[Pál Turán]] in 1941.{{r|turan}} The [[special case]] of the theorem for [[triangle-free graph]]s is known as '''Mantel's theorem'''; it was stated in 1907 by Willem Mantel, a Dutch mathematician.{{r|mantel}}