Théorème de Turán

Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.e. K_r+1 -free) possède au plus le nombre suivant d'arêtes :

${\displaystyle {\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.}$

Cette borne est atteinte par le graphe de Turán T(n,r).

Le cas particulier r = 2, correspond au théorème de Mantel :

Le nombre maximal d'arêtes dans un graphe sans triangle est ${\displaystyle \lfloor n^{2}/4\rfloor .}$

(en) Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ 1941, p. 436-452