UNE ÉNIGME DES ANNÉES 1960 SUR LES GRAPHES SE REFERME

Prenez des points et reliez certaines paires par des traits : les mathématiciens appellent cela un graphe, les points ses sommets et les traits ses arêtes. Un cycle est une boucle fermée qui passe par des sommets distincts et revient à son départ. Une question naturelle : peut-on répartir les arêtes d’un graphe — chacune utilisée exactement une fois — en cycles ?

La réponse est connue depuis longtemps, rappelle l’article : c’est possible exactement quand chaque sommet touche un nombre pair d’arêtes. On appelle ces graphes eulériens. La question suivante est de savoir combien de cycles il faut. Et pour les graphes où les cycles seuls ne suffisent pas, on autorise aussi des arêtes isolées comme morceaux.

La conjecture

Dans les années 1960, Erdős et Gallai ont conjecturé que les arêtes de tout graphe à n sommets peuvent être réparties en un nombre de cycles et d’arêtes isolées au plus proportionnel à n — ce qu’on note O(n). Erdős l’a incluse dans plusieurs de ses recueils de problèmes ouverts. Une conjecture voisine, due à Hajós, demande au plus (n − 1)/2 cycles pour tout graphe eulérien.

On ne peut pas espérer mieux que linéaire : Erdős a montré que certains graphes demandent environ 1,5 n morceaux. Toute la question était de savoir si une constante fois n suffit toujours.

Cinquante ans de bornes qui rampent

Erdős et Gallai avaient eux-mêmes remarqué une méthode simple : retirer à répétition le plus long cycle. Elle donne environ n log n morceaux — et, selon l’article, ce fut la meilleure borne générale pendant près de cinquante ans. Plus récemment, Conlon, Fox et Sudakov l’ont abaissée à n log log n, puis Bucić et Montgomery à n log* n, où log* n — le nombre de fois qu’il faut prendre un logarithme pour descendre sous 1 — croît d’une lenteur inimaginable. Ces approches procédaient par rondes, et chaque ronde coûtait environ n cycles, si bien que le nombre de rondes se glissait toujours dans le décompte final. La conjecture avait aussi été démontrée pour des familles particulières, comme les graphes aléatoires.

Des poids qui paient les boucles

Jaehoon Kim, du KAIST en Corée du Sud, démontre désormais la conjecture : il existe une constante fixe C telle que tout graphe à n sommets se découpe en au plus Cn cycles et arêtes. En corollaire, la conjecture de Hajós est vraie à un facteur constant près.

La preuve abandonne les rondes. Une seule procédure retire cycles et arêtes un à un, et le total est contrôlé par deux quantités qui restent chacune sous une constante fois n.

• Un potentiel fondé sur les degrés. Chaque sommet reçoit un poids qui diminue avec son nombre d’arêtes, en gros 1 / (degré × log² degré). Un cycle est lourd si les poids de ses sommets totalisent au moins 1. Retirer un cycle lourd fait baisser un « potentiel » global d’au moins 1, et ce potentiel part d’au plus une constante fois n. On ne peut donc retirer des cycles lourds que O(n) fois.
• Le nombre de sommets. Quand il ne reste plus de cycle lourd, le graphe est « léger » — et le principal théorème nouveau montre qu’un graphe léger aux degrés élevés contient forcément une région dense, presque fermée sur elle-même. Cette région est découpée en un nombre de cycles et d’arêtes proportionnel à sa taille, après quoi au moins un cinquantième de ses sommets ne gardent qu’au plus deux arêtes et sortent définitivement du jeu. Comme chaque sommet ne peut sortir qu’une fois, cette partie coûte aussi O(n).

Dans les parties denses du graphe, des morceaux de chemins sont refermés en un seul cycle par des chemins de jonction qui passent par des « expanseurs » ; un coloriage aléatoire empêche les chemins de jonction d’un même cycle de se croiser. — Figure 3, Kim (2026), arXiv:2610.07840.

Pour découper ces régions denses, la preuve prolonge la boîte à outils de Bucić et Montgomery sur les « expanseurs » robustes — des graphes où tout ensemble de sommets a beaucoup de voisins — et colorie les sommets au hasard pour que les chemins de liaison d’un même cycle ne se heurtent jamais.

Ce qui reste ouvert

La constante C est énorme, et l’auteur n’a pas cherché à l’optimiser. Trouver la meilleure constante — au moins 1,5 — reste ouvert, tout comme la conjecture exacte de Hajós et une conjecture voisine de Gallai sur le découpage des graphes en chemins. L’astuce des poids ne demande que des poids dont la somme converge, et l’auteur suggère qu’elle pourrait servir à d’autres problèmes de découpage.

Il s’agit d’une prépublication à un seul auteur, pas encore vérifiée par des pairs.

Conflit d’intérêts. L’auteur déclare avoir beaucoup utilisé ChatGPT (OpenAI) et Claude (Anthropic) pour élaborer les arguments et préparer le texte et les figures, et avoir vérifié tous les résultats, dont l’auteur assume l’entière responsabilité. Le texte que vous lisez a, lui aussi, été rédigé par Claude.