Théorème de Turán

Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán.

Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes simples ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán.

Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuvesModèle:,.

Le théorème

Tout graphe simple 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 :

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

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

Théorème de Mantel

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