UNE LIMITE DES RÉSEAUX, DÉSORMAIS PROUVÉE À TOUTE TAILLE
Prenez quelques points et reliez certaines paires par des traits. Les mathématiciens appellent cela un graphe : les points sont ses sommets, les traits ses arêtes, et la distance entre deux sommets est le plus petit nombre d’arêtes à parcourir pour aller de l’un à l’autre. Ajoutez deux règles. Toute paire de sommets doit être à distance 2 au plus — reliés directement, ou par un voisin commun. Et aucune arête ne doit être en trop : supprimez-en une seule, n’importe laquelle, et une paire se retrouve à plus de deux pas. Un tel graphe est dit diamètre-2-critique. Combien d’arêtes peut-il avoir ?
Le plafond de Mantel, et un pari plus audacieux
En 1907, Mantel a démontré qu’un graphe à n sommets sans triangle — sans trois sommets tous reliés entre eux — a au plus ⌊n²/4⌋ arêtes : n au carré divisé par quatre, arrondi à l’entier inférieur. Un seul graphe atteint ce plafond, le graphe biparti complet équilibré : deux groupes de tailles aussi égales que possible, chaque sommet de l’un relié à chaque sommet de l’autre, aucune arête à l’intérieur d’un groupe.
Tout graphe sans triangle auquel on ne peut plus ajouter une arête sans créer de triangle est diamètre-2-critique. L’inverse est faux : certains graphes diamètre-2-critiques contiennent des triangles.
Un graphe diamètre-2-critique à 7 sommets et 9 arêtes, qui contient le triangle v1v3v5. Supprimer v1v3 détruit le seul chemin en deux pas entre v2 et v3 ; supprimer une arête hors du triangle laisse ses extrémités sans aucun chemin en deux pas. — Figure 1, Das & Fox (2026), arXiv:2610.39032.
Le pari était que les triangles ne rapportent rien : un graphe diamètre-2-critique à n sommets a toujours au plus ⌊n²/4⌋ arêtes, et le graphe biparti complet équilibré reste le seul à l’atteindre. Le théorème de Mantel en deviendrait un cas particulier. Pour les 7 sommets de la figure, le plafond est de 12 arêtes.
Une tour de 2
Selon Erdős, rapporté par Zoltán Füredi, la question remonte à des travaux d’Ore dans les années 1960. Ján Plesník a énoncé la borne comme conjecture en 1975 ; Murty et Simon l’ont proposée de leur côté, en ajoutant que le graphe biparti complet équilibré est le seul cas extrême — d’où le nom de conjecture de Murty-Simon. Dans les années 1970 et 1980, des bornes de la forme c·n² se sont resserrées, avec c de plus en plus proche de 1/4.
En 1992, Füredi a démontré la conjecture pour tout n assez grand, avec des méthodes de régularité — des outils très généraux, tirés du lemme de régularité de Szemerédi, dont les garanties ne valent que pour des graphes gigantesques. D’où le prix à payer, la taille de départ : n devait valoir au moins une tour de 2 de hauteur environ 10¹⁴, c’est-à-dire 2 puissance 2 puissance 2…, calculé du haut vers le bas — chaque 2 élevé à la puissance de tout ce qui le surmonte —, avec environ 10¹⁴ chiffres 2 empilés. En dessous de cette taille, seules des familles particulières de graphes avaient été réglées.
Les arêtes contre les arêtes manquantes
La nouvelle preuve, due à Sanjana Das et Jacob Fox, du département de mathématiques de l’université Stanford, vaut pour tout n à partir de 3. Elle utilise un couplage maximal : un ensemble d’arêtes sans sommet commun deux à deux, auquel on ne peut ajouter aucune arête sans que deux d’entre elles se touchent. Un couplage sur n sommets compte au plus ⌊n/2⌋ arêtes.
Le lemme clé : dans un graphe diamètre-2-critique, pour n’importe quel couplage maximal, les arêtes hors du couplage ne sont jamais plus nombreuses que les non-arêtes — les paires de sommets non reliés. Le reste est de l’arithmétique. Les non-arêtes, ce sont toutes les paires moins les arêtes : arêtes moins couplage vaut donc au plus paires moins arêtes ; en regroupant les arêtes d’un même côté, deux fois le nombre d’arêtes vaut au plus le nombre de paires plus la taille du couplage. Avec 10 sommets : 45 paires plus 5 arêtes de couplage au plus font 50, donc 25 arêtes au maximum. Pour tout n, cette somme vaut exactement le double du plafond de Mantel.
Le lemme lui-même est une comptabilité minutieuse. Une non-arête est critique si un seul chemin en deux pas relie ses extrémités, comme les douze non-arêtes de la figure 1. Les auteurs rattachent chaque non-arête critique aux deux arêtes de son chemin, puis découpent le réseau obtenu en morceaux connexes. Un morceau compte au plus une arête de plus que de non-arêtes critiques, et chaque morceau excédentaire doit être compensé par une non-arête non critique. Pour les trouver, les auteurs utilisent des « sorties par échange » : on prend une arête ou une non-arête critique du morceau, et on remplace l’une de ses extrémités par son partenaire dans le couplage. Chaque non-arête non critique est réclamée au plus deux fois, chaque morceau excédentaire en réclame au moins deux : il n’y a donc pas plus de morceaux excédentaires que de non-arêtes non critiques, ce qu’il fallait pour le lemme.
Qui a trouvé quoi
« Cette preuve a été trouvée en majeure partie par une IA, en l’occurrence GPT-5.6 Sol, le 11 août 2026 », écrivent les auteurs dans une courte déclaration sur l’IA. Le modèle a trouvé une preuve complète de la borne ⌊n²/4⌋, que les auteurs ont simplifiée. Pour un nombre pair de sommets, il a aussi démontré que le graphe biparti complet équilibré est le seul cas extrême, en s’appuyant sur un résultat de Sumner sur les graphes dont tout couplage maximal est parfait, c’est-à-dire couvre tous les sommets.
Avec un nombre impair de sommets, aucun couplage n’est parfait, et beaucoup de graphes ont des couplages maximaux qui laissent tous exactement un sommet de côté : l’argument du modèle ne pouvait pas être adapté. Les auteurs ont trouvé une autre preuve du cas d’égalité, valable pour tout n, et ont rédigé l’article eux-mêmes ; un dernier passage par GPT-6 Astra a mené à « quelques modifications mineures ». L’article est une prépublication, pas encore relue par des pairs, et ne mentionne aucune version de la preuve vérifiée par ordinateur.
Retour en 1907
Si un graphe atteint le plafond, l’inégalité clé est une égalité pour tous les couplages maximaux. En choisissant habilement ces couplages, les auteurs montrent qu’un tel graphe est soit une étoile — un sommet relié à tous les autres, rien de plus —, soit dépourvu de toute non-arête critique. Dans un graphe diamètre-2-critique, toute arête d’un triangle se trouve sur un chemin critique : sans non-arête critique, pas de triangle ; une étoile n’en a pas non plus. Un graphe qui atteint le plafond est donc sans triangle, et le dernier pas est le théorème que la conjecture voulait renforcer : celui de Mantel, de 1907, qui laisse le graphe biparti complet équilibré seul au plafond.