Main Page | See live article | Alphabetical index

Tur�n graph

In mathematical graph theory, 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 Kk as a subgraph. An upper bound for the number of edges of T(n, k), typically written as t(n, k), is given by Tur�n's theorem; as a special case, for k = 3, one obtains

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

Also see