Turán's theorem

In graph theory, a branch of mathematics, Turán's theorem is a result on the number of edges in a Turán graph. The Turán graph for given natural numbers n and k, denoted T(n, k), is defined as the extremal graph with n vertices which does not contain the complete graph K_k as a subgraph. The number of edges of T(n, k) is written as t(n, k); it is given by Turán's theorem, that

As a special case, for k = 3, one obtains

Turán graphs were first described and studied by Hungarian mathematician Paul Turán.

See also: extremal graph theory.