TOPICS
Search

Turán's Theorem


Let G(V,E) be a graph with graph vertices V and graph edges E on n graph vertices without a (k+1)-clique. Then

 t(n,k)<=((k-1)n^2)/(2k),

where t(n,k) is the edge count. (Note that the convention of Aigner (1995) of considering k-cliques has been replaced with the apparently slightly more standard indexing by considering (k+1)-cliques, providing consistency with the usual definition of Turán graphs.)

The Turán graph T(n,k) is defined as the unique graph without a (k+1)-clique having the maximum possible number of graph edges, namely

 t(n,k)=|_((k-1)n^2)/(2k)_|,

where |_x_| denotes the floor function.


See also

Clique, Erdős-Stone Theorem, Extremal Graph Theory, Turán Graph

Explore with Wolfram|Alpha

References

Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.Pach, J. and Agarwal, P. K. "Forbidden Complete Subgraphs." Combinatorial Geometry. New York: Wiley, pp. 119-125, 1995.

Referenced on Wolfram|Alpha

Turán's Theorem

Cite this as:

Weisstein, Eric W. "Turán's Theorem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TuransTheorem.html

Subject classifications