La théorie extrémale des graphes cherche à déterminer le nombre maximum ou minimum d’arêtes que peut avoir un graphe de $n$ sommets tout en satisfaisant une certaine propriété.
Le théorème de Turán est le point de départ de ce domaine. Il s’intéresse à la propriété d’être « sans clique ».
- Une clique de taille $r$, notée $K_r$, est un sous-ensemble de $r$ sommets où chaque sommet est connecté à tous les autres. Un $K_3$ est un triangle.
- Un graphe est dit sans $K_{r+1}$ s’il ne contient aucune clique de taille $r+1$.
La question est donc : quel est le nombre maximal d’arêtes qu’un graphe à $n$ sommets peut avoir sans contenir de $K_{r+1}$ ?
Le nombre maximal d’arêtes dans un graphe à $n$ sommets qui ne contient pas de clique de taille $r+1$ est noté $ex(n, K_{r+1})$ et est atteint par un graphe unique appelé le graphe de Turán, noté $T(n, r)$.
Ce nombre d’arêtes est approximativement : $$ ex(n, K_{r+1}) \approx \left(1 – \frac{1}{r}\right) \frac{n^2}{2} $$
Le Graphe de Turán $T(n, r)$
Le graphe qui réalise ce maximum d’arêtes a une structure très particulière :
- On partitionne les $n$ sommets en $r$ ensembles (ou « parts »), $V_1, V_2, \dots, V_r$.
- La taille de ces ensembles est la plus équilibrée possible. Si $n = q \cdot r + s$ (avec $0 \le s < r$), alors $s$ ensembles auront une taille de $q+1$ et $r-s$ ensembles auront une taille de $q$.
- On relie par une arête deux sommets si et seulement s’ils appartiennent à des ensembles différents. Il n’y a aucune arête à l’intérieur d’un même ensemble.
Ce graphe est un graphe $r$-parti complet. Par construction, il ne peut pas contenir de clique de taille $r+1$, car d’après le principe des tiroirs, si on choisit $r+1$ sommets, au moins deux d’entre eux doivent se trouver dans le même ensemble et ne sont donc pas connectés.
Exemple : $T(5, 2)$
C’est le graphe sans triangle ($K_3$-free, donc $r=2$) à 5 sommets avec le plus d’arêtes. On divise les 5 sommets en 2 parts de tailles 3 et 2. On relie chaque sommet de la première part à chaque sommet de la seconde. On obtient 6 arêtes. Ajouter n’importe quelle arête créerait inévitablement un triangle.