Turán's Theorem

Let  be a graph with graph vertices  and graph edges  on  graph vertices without a -clique. Then

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

The Turán graph  is defined as the unique graph without a -clique having the maximum possible number of graph edges, namely

where  denotes the floor function.

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.