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[modifier | modifier le code]
Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.e. Kr+1 -free) possède au plus le nombre suivant d'arêtes :
Cette borne est atteinte par le graphe de Turán T(n,r).
Théorème de Mantel[modifier | modifier le code]
Le cas particulier r = 2, correspond au théorème de Mantel :
Le nombre maximal d'arêtes dans un graphe sans triangle est
Bibliographie[modifier | modifier le code]
(en) Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48, , p. 436-452
Notes et références[modifier | modifier le code]
- Martin Aigner et Günter M. Ziegler, Raisonnements divins, Springer (lire en ligne), p. 235-240.
- (en) Martin Aigner, « Turán's graph theorem », Am. Math. Monthly, vol. 102, , p. 808-816 (lire en ligne) (prix Paul R. Halmos-Lester R. Ford 1996).
