EINE GRENZE FÜR NETZWERKE, JETZT FÜR JEDE GRÖSSE BEWIESEN

Man nehme ein paar Punkte und verbinde einige Paare davon durch Linien. Mathematiker nennen das einen Graphen: Die Punkte sind seine Knoten, die Linien seine Kanten, und der Abstand zwischen zwei Knoten ist die kleinste Zahl von Kanten, die man braucht, um vom einen zum anderen zu gelangen. Nun fügt man zwei Regeln hinzu. Jedes Knotenpaar muss höchstens Abstand 2 haben – direkt verbunden oder über einen gemeinsamen Nachbarn. Und keine Kante darf überflüssig sein: Löscht man irgendeine einzelne, liegt danach irgendein Paar mehr als zwei Schritte auseinander. Ein solcher Graph heißt durchmesser-2-kritisch. Wie viele Kanten kann er haben?

Mantels Obergrenze und eine kühnere Vermutung

1907 bewies Mantel, dass ein Graph mit n Knoten ohne Dreieck – ohne drei Knoten, die alle miteinander verbunden sind – höchstens ⌊n²/4⌋ Kanten hat: n zum Quadrat geteilt durch vier, auf eine ganze Zahl abgerundet. Nur ein Graph erreicht diese Obergrenze, der balancierte vollständige bipartite Graph: zwei möglichst gleich große Gruppen, jeder Knoten der einen mit jedem Knoten der anderen verbunden, keine Kante innerhalb einer Gruppe.

Jeder dreiecksfreie Graph, der keine weitere Kante aufnehmen kann, ohne ein Dreieck zu erzeugen, ist durchmesser-2-kritisch. Die Umkehrung gilt nicht: Manche durchmesser-2-kritischen Graphen enthalten Dreiecke.

Sieben schwarze Punkte, verbunden durch neun violette Linien, von denen drei ein großes Dreieck bilden.

Ein durchmesser-2-kritischer Graph mit 7 Knoten und 9 Kanten, der das Dreieck v1v3v5 enthält. Das Löschen von v1v3 zerstört den einzigen Weg in zwei Schritten zwischen v2 und v3; das Löschen einer Kante außerhalb des Dreiecks lässt ihre Enden ohne Weg in zwei Schritten zurück. — Abbildung 1, Das & Fox (2026), arXiv:2610.39032.

Die Vermutung lautete, dass Dreiecke nichts einbringen: Ein durchmesser-2-kritischer Graph mit n Knoten hat trotzdem höchstens ⌊n²/4⌋ Kanten, und der balancierte vollständige bipartite Graph ist weiterhin der einzige, der diesen Wert erreicht. Mantels Satz würde daraus als Spezialfall folgen. Für die 7 Knoten der Abbildung liegt die Obergrenze bei 12 Kanten.

Ein Turm aus Zweien

Laut Erdős, wie Zoltán Füredi berichtet, geht die Frage auf Arbeiten von Ore in den 1960er-Jahren zurück. Ján Plesník formulierte die Kantenschranke 1975 als Vermutung; Murty und Simon schlugen sie unabhängig davon vor und fügten hinzu, dass der balancierte vollständige bipartite Graph der einzige Extremfall ist – daher die Murty-Simon-Vermutung. In den 1970er- und 1980er-Jahren sanken Schranken der Form c·n² allmählich, mit c immer näher an 1/4.

1992 bewies Füredi die Vermutung für jedes hinreichend große n, mit Regularitätsmethoden – Werkzeugen, die aus Szemerédis Regularitätslemma abgeleitet sind. Der Preis war die Startgröße: n musste mindestens ein Turm aus Zweien mit einer Höhe von ungefähr 10¹⁴ sein, also 2 hoch 2 hoch 2 …, von oben nach unten ausgerechnet – jede 2 hoch alles, was über ihr steht –, mit etwa 10¹⁴ Zweien im Stapel. Unterhalb dieser Größe waren nur spezielle Familien von Graphen geklärt.

Kanten gegen fehlende Kanten

Der neue Beweis von Sanjana Das und Jacob Fox vom Fachbereich Mathematik der Stanford University gilt für jedes n ab 3. Er verwendet ein maximales Matching: eine Menge von Kanten, von denen keine zwei einen Knoten gemeinsam haben und zu der sich keine weitere Kante hinzufügen lässt, ohne dass zwei davon zusammentreffen. Ein Matching auf n Knoten enthält höchstens ⌊n/2⌋ Kanten.

Das Schlüssellemma: In einem durchmesser-2-kritischen Graphen sind für jedes maximale Matching die Kanten außerhalb des Matchings niemals zahlreicher als die Nicht-Kanten – die Knotenpaare, die nicht verbunden sind. Der Rest ist Arithmetik. Das Doppelte der Kantenzahl ist höchstens die Zahl der Paare plus die Größe des Matchings. Bei 10 Knoten: 45 Paare plus höchstens 5 Matching-Kanten ergeben 50, also höchstens 25 Kanten. Für jedes n ergibt diese Summe genau das Doppelte von Mantels Obergrenze.

Das Lemma selbst ist sorgfältige Buchführung. Eine Nicht-Kante ist kritisch, wenn ein einziger Weg in zwei Schritten ihre Enden verbindet, wie bei allen zwölf Nicht-Kanten von Abbildung 1. Die Autoren ordnen jede kritische Nicht-Kante den beiden Kanten ihres Weges zu und zerlegen das entstehende Geflecht in zusammenhängende Stücke. Ein Stück enthält höchstens eine Kante mehr als kritische Nicht-Kanten, und jedes Stück mit diesem Überschuss muss durch eine nicht kritische Nicht-Kante bezahlt werden. Um diese zu finden, verwenden die Autoren Wechselausgänge (switch exits): Man nimmt eine Kante oder kritische Nicht-Kante des Stücks und tauscht eines ihrer Enden gegen dessen Partner im Matching aus. Jede nicht kritische Nicht-Kante wird höchstens zweimal beansprucht, jedes Überschussstück stellt mindestens zwei Ansprüche, und die Rechnung geht auf.

Wer was gefunden hat

„Dieser Beweis wurde größtenteils von einer KI gefunden, genauer gesagt von GPT-5.6 Sol am 11. August 2026“, schreiben die Autoren in einer kurzen KI-Erklärung. Das Modell fand einen vollständigen Beweis der Schranke ⌊n²/4⌋, den sie vereinfachten. Für eine gerade Zahl von Knoten bewies es außerdem, dass der balancierte vollständige bipartite Graph der einzige Extremfall ist, gestützt auf eine von Sumner bewiesene Tatsache über Graphen, in denen jedes maximale Matching perfekt ist, also jeden Knoten abdeckt.

Bei einer ungeraden Zahl von Knoten ist kein Matching perfekt, und bei vielen Graphen verfehlt jedes maximale Matching genau einen Knoten: Das Argument des Modells ließ sich nicht anpassen. Die Autoren fanden einen anderen Beweis für den Gleichheitsfall, gültig für jedes n, und schrieben die Arbeit selbst; ein abschließender Durchgang mit GPT-6 Astra führte zu „ein paar kleinen Änderungen“. Die Arbeit ist ein Preprint, noch nicht begutachtet, und sie erwähnt keine computergeprüfte Fassung des Arguments.

Zurück zu 1907

Erreicht ein Graph die Obergrenze genau, ist die Schlüsselungleichung für jedes maximale Matching eine Gleichung. Durch geschickte Wahl von Matchings zeigen die Autoren, dass ein solcher Graph entweder ein Stern ist – ein Knoten, der mit allen anderen verbunden ist, sonst nichts – oder überhaupt keine kritische Nicht-Kante hat. In einem durchmesser-2-kritischen Graphen liegt jede Kante eines Dreiecks auf irgendeinem kritischen Weg, also bedeutet keine kritische Nicht-Kante auch kein Dreieck; ein Stern hat ebenfalls keines. Ein Graph, der die Grenze erreicht, ist daher dreiecksfrei, und der letzte Schritt ist der Satz, den die Vermutung verschärfen wollte: Mantels Ergebnis von 1907, das den balancierten vollständigen bipartiten Graphen allein an der Obergrenze lässt.