EIN GRAPHENRÄTSEL AUS DEN 1960ERN SCHLIESST SICH ENDLICH

Nehmen Sie einige Punkte und verbinden Sie manche Paare davon mit Linien: Mathematiker nennen das einen Graphen, die Punkte seine Knoten und die Linien seine Kanten. Ein Kreis ist eine geschlossene Schleife, die verschiedene Knoten besucht und zu ihrem Ausgangspunkt zurückkehrt. Eine naheliegende Frage ist, ob sich die Kanten eines Graphen – jede Kante genau einmal verwendet – in Kreise aufteilen lassen.

Die Antwort ist seit Langem bekannt, wie die Arbeit in Erinnerung ruft: Es ist genau dann möglich, wenn jeder Knoten eine gerade Zahl von Kanten berührt. Solche Graphen heißen eulersch. Die nächste Frage ist, wie viele Kreise man braucht. Und für Graphen, bei denen Kreise allein nicht genügen, lässt man auch einzelne Kanten als Teile zu.

Die Vermutung

In den 1960er-Jahren vermuteten Erdős und Gallai, dass sich die Kanten jedes Graphen mit n Knoten in eine Zahl von Kreisen und einzelnen Kanten aufteilen lassen, die höchstens proportional zu n ist – geschrieben O(n). Erdős nahm sie in mehrere seiner Sammlungen offener Probleme auf. Eine verwandte Vermutung von Hajós verlangt höchstens (n − 1)/2 Kreise in jedem eulerschen Graphen.

Linear ist das Beste, worauf man hoffen kann: Erdős zeigte, dass manche Graphen etwa 1,5 n Teile brauchen. Die Frage war, ob stets eine Konstante mal n genügt.

Fünfzig Jahre langsam kriechender Schranken

Erdős und Gallai selbst bemerkten eine einfache Methode: wiederholt den längsten Kreis entfernen. Sie liefert etwa n log n Teile – und das blieb laut der Arbeit fast fünfzig Jahre lang die beste allgemeine Schranke. In jüngerer Zeit senkten Conlon, Fox und Sudakov sie auf n log log n, dann Bucić und Montgomery auf n log* n, wobei log* n – die Zahl, wie oft man einen Logarithmus nehmen muss, um unter eins zu kommen – unvorstellbar langsam wächst. Diese Ansätze arbeiteten in Runden, und jede Runde kostete etwa n Kreise, sodass die Zahl der Runden stets in die Endabrechnung einfloss. Für spezielle Familien, etwa Zufallsgraphen, war die Vermutung bereits bewiesen.

Gewichte, die Schleifen bezahlen

Jaehoon Kim vom KAIST in Südkorea beweist die Vermutung nun: Es gibt eine feste Konstante C, sodass sich jeder Graph mit n Knoten in höchstens Cn Kreise und Kanten zerlegen lässt. Als Folgerung gilt die Vermutung von Hajós bis auf einen konstanten Faktor.

Der Beweis verzichtet auf Runden. Ein einziges Verfahren entfernt Kreise und Kanten nacheinander, und die Gesamtzahl wird durch zwei Größen kontrolliert, die jeweils unter einer Konstante mal n bleiben.

• Ein Potenzial auf Grundlage der Grade. Jeder Knoten erhält ein Gewicht, das mit seiner Kantenzahl schrumpft, ungefähr 1 / (Grad × log² Grad). Ein Kreis ist schwer, wenn sich die Gewichte seiner Knoten zu mindestens 1 summieren. Das Entfernen eines schweren Kreises senkt ein Gesamt-„Potenzial“ um mindestens 1, und dieses Potenzial beträgt anfangs höchstens eine Konstante mal n. Schwere Kreise lassen sich also nur O(n)-mal entfernen.
• Die Zahl der Knoten. Wenn kein schwerer Kreis mehr übrig ist, ist der Graph „leicht“ – und der wichtigste neue Satz zeigt, dass ein leichter Graph mit großen Graden eine dichte, fast abgeschlossene Region enthalten muss. Diese Region wird in eine zu ihrer Größe proportionale Zahl von Kreisen und Kanten zerlegt, wonach mindestens ein Fünfzigstel ihrer Knoten nur noch höchstens zwei Kanten hat und endgültig ausscheidet. Da jeder Knoten nur einmal ausscheiden kann, kostet auch dieser Teil O(n).

In dichten Teilen des Graphen werden Pfadstücke durch Verbindungspfade, die durch „Expander“ geführt werden, zu einem einzigen Kreis geschlossen; eine zufällige Färbung hält die Verbindungspfade eines Kreises auseinander. — Abbildung 3, Kim (2026), arXiv:2610.07840.

Um diese dichten Regionen zu zerlegen, erweitert der Beweis den Werkzeugkasten von Bucić und Montgomery mit robusten „Expandern“ – Graphen, in denen jede Knotenmenge viele Nachbarn hat – und färbt Knoten zufällig, damit die Verbindungspfade desselben Kreises nie kollidieren.

Was noch offen ist

Die Konstante C ist enorm, und der Autor hat nicht versucht, sie zu optimieren. Die beste Konstante – mindestens 1,5 – zu finden, bleibt offen, ebenso die exakte Vermutung von Hajós und eine verwandte Vermutung von Gallai über die Zerlegung von Graphen in Pfade. Der Gewichtungstrick braucht nur Gewichte, deren Summe konvergiert, und der Autor regt an, dass er auch bei anderen Zerlegungsproblemen helfen könnte.

Es handelt sich um ein Preprint eines einzelnen Autors, das noch nicht durch Peer-Review geprüft wurde.

Interessenkonflikt. Der Autor erklärt, dass er ChatGPT (OpenAI) und Claude (Anthropic) ausgiebig genutzt hat, um die Argumente zu entwickeln sowie Text und Abbildungen zu erstellen, und dass er alle Ergebnisse überprüft hat und die volle Verantwortung für die Arbeit übernimmt. Auch der Text, den Sie gerade lesen, wurde von Claude geschrieben.