|
|
In graph theory, Turán's theorem is a result on the number of edges in a Ks+1-free graph. Suppose we have given the graph Kn. We can easily obtain an Ks+1-free graph by deleting some edges.
For example, we can partition the set of vertices into s parts of equal size (or almost equal size). Then we delete all the edges which take place in only one part. By this construction we obtain the Turán graph T(n,s). And we have to delete the fraction 1/s of all the edges in Kn. So there remains the fraction (s-1)/s of all the edges in Kn.
Turán's theorem now says that this is best possible:
Turán [1941]: Let G be any subgraph of Kn such that G is Ks+1 -free. Then the number of edges in G is at most
- <math>\frac{s-1}{s}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{s} \right) \cdot\frac{n^2}{2}.<math>
An equivalent formulation is the following:
Turán [1941]: Among the n-vertex simple graphs with no r+1-cliques, T(n,r) has the maximum number of edges.
Turán graphs were first described and studied by Hungarian mathematician Paul Turán in 1941.
As a special case, for s = 2, one obtains Mantel's theorem:
Mantel [1907] The maximum number of edges in an n-vertex triangle-free simple graph is <math>\lfloor n^2/4 \rfloor.<math>
With other words: We have to delete half of the edges in Kn to obtain an triangle-free graph.
See also
- Extremal graph theory
- West, D. "Introduction to Graph Theory", Second Edition, Prentice Hall