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 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 preuves[1],[2].

Le théorème

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).

Théorème de Mantel

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 .}$

Bibliographie

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

Notes et références

1. Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer (lire en ligne), p. 235-240.
2. (en) Martin Aigner, « Turán's graph theorem », Am. Math. Monthly, vol. 102,‎ 1995, p. 808-816 (lire en ligne) (prix Paul R. Halmos-Lester R. Ford 1996).