Paper Talk - Die Cycle-Double-Cover-Vermutung

Im Juli 2026 veröffentlichte OpenAI einen Beweis der Cycle-Double-Cover-Vermutung, eines seit rund 50 Jahren offenen Problems der Graphentheorie. Bemerkenswert ist dabei weniger der Text selbst als seine Herkunft: Erzeugt wurde er nach Angaben von OpenAI von einem Sprachmodell, GPT-5.6 Sol Ultra, verteilt auf 64 parallel arbeitende Teilagenten (Subagents) und in weniger als einer Stunde. In diesem Paper Talk schauen wir uns zuerst die Vermutung selbst an, die überraschend anschaulich ist, und danach, was an diesem Beweis und an seiner Entstehung interessant ist.

Die Vermutung: jede Kante genau zweimal

Ein Graph besteht aus Knoten und Kanten, also aus Punkten und Verbindungen zwischen ihnen. Ein Kreis ist ein geschlossener Rundweg, der keinen Knoten doppelt besucht und am Ausgangspunkt endet, etwa das Dreieck $1\to 2\to 3\to 1$.

Die Cycle-Double-Cover-Vermutung (auf Deutsch etwa „Kreis-Doppelüberdeckung", kurz CDC) fragt nach einer Familie von Kreisen mit einer sehr speziellen Eigenschaft: Jede Kante des Graphen soll in genau zwei dieser Kreise vorkommen. Nicht einmal, nicht dreimal, sondern exakt zweimal. Die Vermutung behauptet, dass eine solche Familie immer existiert, sofern der Graph eine harmlos klingende Bedingung erfüllt, auf die wir gleich kommen.

Ein Mini-Beispiel: Beim Dreieck mit den drei Kanten $12$, $23$, $31$ nehmen wir einfach denselben Kreis zweimal. Dann ist jede der drei Kanten in genau zwei Kreisen enthalten. Fertig. Interessant wird es erst bei Graphen, bei denen man nicht so billig davonkommt.

Ein etwas ehrlicheres Beispiel, das ohne den Trick „derselbe Kreis zweimal" auskommt, ist der Diamant: zwei Dreiecke, die sich eine gemeinsame Kante teilen. Nennen wir die Knoten $o$ (oben) und $u$ (unten) für die geteilte Kante sowie $l$ (links) und $r$ (rechts). Die fünf Kanten sind $ou$, $ol$, $lu$, $or$, $ru$. Hier reichen drei verschiedene Kreise:

• linkes Dreieck: $o\to l\to u\to o$ mit den Kanten $ol$, $lu$, $ou$
• rechtes Dreieck: $o\to r\to u\to o$ mit den Kanten $or$, $ru$, $ou$
• äußerer Rand: $l\to o\to r\to u\to l$ mit den Kanten $ol$, $or$, $ru$, $lu$

Die geteilte Kante $ou$ liegt in beiden Dreiecken, jede der vier Außenkanten in einem Dreieck und im Rand. Also liegt jede Kante in genau zwei Kreisen.

Dieses Beispiel verrät auch, woher die „zwei" eigentlich kommt. Zeichnet man einen Graphen ohne Überschneidungen in die Ebene, so zerlegt er sie in Gebiete (englisch faces), und jede Kante grenzt an genau zwei davon. Der Rand jedes Gebiets ist ein Kreis. Nimmt man also alle Gebietsränder zusammen, wird jede Kante genau zweimal überdeckt. Für Graphen, die sich überschneidungsfrei zeichnen lassen (die planaren Graphen), liefern die Gebiete somit ganz von selbst eine Doppelüberdeckung. Die Vermutung behauptet, dass es diese immer gibt, auch wenn sich der Graph nicht so schön in die Ebene legen lässt.

Warum „brückenlos"?

Die Bedingung lautet: Der Graph muss brückenlos sein. Eine Brücke ist eine Kante, deren Entfernen den Graphen in zwei Teile zerfallen lässt. Der einzige Weg von der einen Seite zur anderen führt über genau diese Kante.

Auch das lässt sich an einem kleinen Bild festmachen. Verbindet man zwei Dreiecke durch eine einzige Kante, so ist gerade diese Verbindungskante eine Brücke: Nimmt man sie weg, zerfällt der Graph in seine beiden Dreiecke, und es gibt keinen Weg mehr von links nach rechts.

Warum ist das wichtig? Eine Brücke kann in keinem einzigen Kreis liegen, denn ein Kreis müsste sie wieder verlassen, und dafür gäbe es keine zweite Verbindung. Wer über die Brücke von links nach rechts läuft, kommt nur über dieselbe Brücke wieder zurück, und dann ist es kein Kreis mehr, weil eine Kante doppelt benutzt würde. Läge in einem Graphen also eine Brücke, würde diese Kante von null Kreisen überdeckt statt von zweien. Für Graphen mit Brücken ist die Vermutung damit von vornherein aussichtslos. Genau deshalb schränkt man auf brückenlose Graphen ein, und die Vermutung sagt: Bei diesen klappt es immer. Die beiden Dreiecke für sich genommen sind übrigens brückenlos, jedes hat wie oben seine eigene Doppelüberdeckung; erst die verbindende Kante bringt das Problem hinein.

Der Trick mit den Farben

Für eine große Klasse von Graphen ist die Aussage leicht zu zeigen, und dieser Fall verrät auch, wo die eigentliche Schwierigkeit steckt. Betrachten wir kubische Graphen, bei denen jeder Knoten genau drei Kanten hat, als konkretes Beispiel den vollständigen Graphen $K_4$ mit den vier Knoten $1,2,3,4$, bei dem je zwei Knoten verbunden sind (sechs Kanten insgesamt).

Wir färben die sechs Kanten mit drei Farben so, dass an jedem Knoten alle drei Farben genau einmal auftreten:

• rot: $\{12, 34\}$
• grün: $\{13, 24\}$
• blau: $\{14, 23\}$

Kontrolle an Knoten $1$: Die Kanten $12$ (rot), $13$ (grün), $14$ (blau) tragen wirklich alle drei Farben. Für die übrigen Knoten geht die Rechnung genauso auf.

Jetzt der Trick: Wir nehmen jeweils zwei Farbklassen zusammen. Weil an jedem Knoten genau eine Kante jeder Farbe hängt, hat in einer solchen Vereinigung jeder Knoten den Grad zwei, und ein Graph, in dem jeder Knoten Grad zwei hat, zerfällt in Kreise. Konkret:

• rot $\cup$ grün $= \{12, 24, 34, 13\}$, das ist der Kreis $1\to 2\to 4\to 3\to 1$
• rot $\cup$ blau $= \{12, 23, 34, 14\}$, das ist der Kreis $1\to 2\to 3\to 4\to 1$
• grün $\cup$ blau $= \{13, 23, 24, 14\}$, das ist der Kreis $1\to 3\to 2\to 4\to 1$

Diese drei Kreise sind bereits die gesuchte Doppelüberdeckung. Der Grund ist eine einfache Buchführung: Jede Kante trägt genau eine Farbe und taucht deshalb in genau den zwei Vereinigungen auf, die diese Farbe beteiligen. Also liegt jede Kante in genau zwei Kreisen. Die Kontrollrechnung Kante für Kante:

Dieselbe Konstruktion funktioniert für jeden kubischen Graphen, dessen Kanten sich mit drei Farben so färben lassen. Für diese Graphen ist die Vermutung also kein Problem.

Wo es schwierig wird: Snarks

Damit verschiebt sich die Frage: Was ist mit kubischen Graphen, die sich nicht mit drei Farben färben lassen? Man kann zeigen, dass ein kleinstmögliches Gegenbeispiel zur Vermutung, falls es eines gäbe, zwangsläufig kubisch und brückenlos sein müsste und sich nicht mit drei Farben kantenfärben ließe. Solche Graphen tragen den kuriosen Namen Snark. Der bekannteste und älteste ist der Petersen-Graph, der bereits 1891 beschrieben wurde.

Das ist der eigentliche Kern des Problems: Die ganze Vermutung hängt allein an den Snarks. Gilt sie für alle Snarks, gilt sie für jeden brückenlosen Graphen. Genau diese Graphen entziehen sich aber dem bequemen Farbtrick von oben, und deshalb blieb die Vermutung ein halbes Jahrhundert lang offen. Formuliert wurde sie unabhängig von mehreren Mathematikern, unter anderem von George Szekeres (1973), Alon Itai und Michael Rodeh (1978), Paul Seymour (1979) und William Tutte; über die Jahre gab es viele Teilresultate für Spezialfälle, etwa für planare Graphen, und mehrere angekündigte Beweise, die sich später als lückenhaft erwiesen und zurückgezogen wurden.

Der Beweis von OpenAI

Nach Darstellung von OpenAI wurde GPT-5.6 Sol Ultra mit der Aufgabe konfrontiert, einen Beweis zu finden. Der Auftrag gab ausdrücklich vor, von der Existenz eines Beweises auszugehen und mindestens acht Stunden zu arbeiten, bevor überhaupt an ein Aufgeben zu denken sei. Tatsächlich lieferte das System nach eigenen Angaben in weniger als einer Stunde ab, verteilt auf 64 parallel arbeitende Teilagenten. Das veröffentlichte PDF ist nur drei Seiten lang, nennt als Autor das Modell selbst und enthält einen eigenen Abschnitt „Statement of AI use", demzufolge der Beweis vollständig von GPT-5.6 Sol Ultra stammt und lediglich das Aufschreiben in LaTeX von einem zweiten Werkzeug übernommen wurde.

Wichtig ist, was das nicht heißt: Es handelt sich nicht um einen maschinellen Beweis im klassischen Sinn, der eine Aussage durch das Durchrechnen vieler Einzelfälle am Computer absichert, wie es etwa beim Vierfarbensatz geschah. Der Beweis hier ist ein kurzer, von Hand lesbarer Text mit klassischen mathematischen Argumenten. Neu ist nicht die Methode, sondern der Umstand, dass eine KI ihn gefunden und aufgeschrieben hat.

Das Bemerkenswerte ist zudem, wie elementar der Beweis ausfällt. Mit dem Farbtrick von oben als Ausgangspunkt lässt er sich tatsächlich nachvollziehen, und genau das tun wir jetzt.

Die Idee: ein Fluss statt einer Färbung

Der Farbtrick scheitert bei Snarks daran, dass es keine Dreifärbung gibt. Der Beweis ersetzt die Färbung deshalb durch etwas, das immer existiert.

Statt dreier Farben nimmt man acht Etiketten: alle Bit-Tripel von $000$ bis $111$. Addieren bedeutet dabei bitweises exklusives Oder (XOR), also zum Beispiel $001 + 011 = 010$. Mathematisch ist das die Gruppe $\Gamma = (\mathbb{Z}/2)^3$. Statt einer Färbung fordert man nun einen nowhere-zero flow, also einen Fluss mit Werten in der Gruppe $\Gamma$: Jede Kante bekommt ein Etikett ungleich $000$, so dass an jedem Knoten die anliegenden Etiketten zusammen $000$ ergeben. Über $\mathbb{F}_2$ gilt $-1 = 1$, weshalb die Kantenrichtung keine Rolle spielt und die Flussbedingung schlicht lautet: Summe an jedem Knoten gleich $000$. An einem Knoten mit den drei Kanten $x, y, z$ heißt das

$x + y + z = 000, \quad \text{also} \quad z = x + y.$

Ein Beispiel: Ist $x = 001$ und $y = 010$, so muss $z = 011$ sein. Alle drei Etiketten sind ungleich $000$ und paarweise verschieden, denn wären zwei gleich, käme als Summe $000$ heraus, was verboten ist.

Der entscheidende Punkt: So ein Fluss existiert für jeden brückenlosen Graphen, auch für jeden Snark. Das ist ein klassisches Ergebnis, das sogenannte 8-Fluss-Theorem, und hier wird zum zweiten Mal benutzt, dass der Graph brückenlos ist. Diesen Baustein erfindet der Beweis nicht, er stützt sich darauf. Eine Dreifärbung wäre übrigens ein besonders schöner solcher Fluss, aber Snarks haben eben nur den Fluss und nicht die Färbung.

Am $K_4$ von oben sieht man diesen Zusammenhang unmittelbar. Schreibt man die drei Farben als Etiketten, rot als $001$, grün als $010$ und blau als $011$, so hat jeder Knoten genau die drei Etiketten $001$, $010$, $011$, und deren XOR ist $001 + 010 + 011 = 000$. Die Färbung ist damit bereits ein nowhere-zero flow. Bei einem Snark gibt es diese schöne, an jedem Knoten gleich aussehende Färbung nicht mehr; ein Fluss aus den acht Etiketten existiert aber trotzdem, er verteilt die Werte nur unregelmäßiger über den Graphen. Genau diese schwächere, aber immer vorhandene Struktur nimmt der Beweis als Ausgangspunkt.

Von Paaren zu Kreisen

Ein Fluss allein liefert noch keine Kreise. Der eigentliche Kniff, im Paper Lemma 2.1, besteht darin, an jede Kante nicht ein einzelnes Etikett zu hängen, sondern ein Paar $P_e = \{p, q\} \subseteq \Gamma$, und dabei nur eine lokale Bedingung zu verlangen: Für jeden Knoten $v$ und jedes Etikett $s \in \Gamma$ soll die Anzahl der an $v$ anliegenden Kanten $e$ mit $s \in P_e$ gleich null oder zwei sein.

Warum genügt das? Für ein festes Etikett $s$ betrachte man die Kantenmenge $M_s = \{e : s \in P_e\}$. Nach der Bedingung hat jeder Knoten in $M_s$ den Grad null oder zwei, also ist $M_s$ 2-regulär und damit eine disjunkte Vereinigung von Kreisen. Weil jedes Paar $P_e$ genau zwei Etiketten enthält, liegt jede Kante in genau zwei der Mengen $M_s$. Die Kreise aller $M_s$ zusammen überdecken somit jede Kante genau zweimal, und das ist die gesuchte Doppelüberdeckung.

Das ist nichts anderes als der Farbtrick in allgemeinerer Form. Eine echte Dreifärbung entspricht den Paaren $\{000, 001\}$, $\{000, 010\}$ und $\{001, 010\}$ für die drei Farben; die zugehörigen Kantenmengen sind genau die drei Farbpaar-Vereinigungen von oben. Der Beweis sagt aber: Die Paare müssen gar nicht von einer Färbung stammen. Irgendwelche Paare mit der Null-oder-zwei-Eigenschaft reichen. Das ist die neue Idee, die den Fall der Snarks knackt.

Solche Paare lassen sich lokal aus dem Fluss ablesen. An einem Knoten mit den Flusswerten $x, y, z$ und einem frei wählbaren Startwert $t$ vergibt man an die drei Kanten die Paare

$\{t,\ t+x\}, \quad \{t+x,\ t+z\}, \quad \{t,\ t+z\}.$

Mit $x = 001$, $y = 010$, $z = 011$ und $t = 000$ sind das $\{000, 001\}$, $\{001, 011\}$ und $\{000, 011\}$. Man prüft leicht nach: $000$ steckt in Paar eins und drei, $001$ in Paar eins und zwei, $011$ in Paar zwei und drei, jedes andere Etikett in keinem. Jedes Etikett kommt also null oder zweimal vor, und das für jeden Startwert $t$.

Die beiden Enden müssen sich einigen

Ein Problem bleibt. Jede Kante $e = uv$ hat zwei Endknoten, und jeder schlägt mit seinem eigenen Startwert $t_u$ beziehungsweise $t_v$ ein Paar für die gemeinsame Kante vor. Für eine widerspruchsfreie Beschriftung müssen beide Enden dasselbe Paar liefern. Der Beweis zeigt, dass genau dann ein globales Etikettenpaar existiert, wenn sich Startwerte $t_v \in \Gamma$ und Bits $\varepsilon_e \in \mathbb{F}_2$ finden lassen mit

$t_u + t_v + \varepsilon_e\, f(e) = d_e \qquad (e = uv),$

wobei $d_e \in \Gamma$ aus den lokalen Daten an den beiden Enden festliegt. Anschaulich sagt die Gleichung: Die beiden von $u$ und $v$ vorgeschlagenen Paare für die Kante $e$ stimmen genau dann überein, wenn sich ihr Unterschied durch die Startwerte $t_u, t_v$ und ein optionales Umklappen $\varepsilon_e$ ausgleichen lässt. Über alle Kanten zusammen ist das ein großes lineares Gleichungssystem über $\mathbb{F}_2$, mit den Startwerten und den Umklapp-Bits als Unbekannten.

Wann ist so ein Gleichungssystem lösbar? Ein lineares System hat genau dann keine Lösung, wenn sich aus seinen Gleichungen ein Widerspruch zusammenbauen lässt, also eine Kombination einiger Gleichungen, deren linke Seiten sich vollständig wegheben, während die rechten Seiten in der Summe nicht null ergeben. Salopp gesagt: Man addiert geschickt ein paar der Gleichungen und erhält $0 = 1$. Solange das nie passieren kann, ist das System lösbar. Über $\mathbb{F}_2$ ist diese Faustregel ein exakter Satz, die sogenannte Fredholm-Alternative. Der Beweis muss also nur zeigen, dass sich hier nie ein solcher Widerspruch bauen lässt.

Die Werkzeuge dafür sind Dualvektoren, auch Linearformen genannt. Ein Dualvektor $\eta$ ordnet jedem Etikett einen Wert $0$ oder $1$ zu, und zwar verträglich mit der XOR-Addition: $\eta(a + b) = \eta(a) + \eta(b)$. Man kann sich $\eta$ als eine feste Ja/Nein-Frage an die Etiketten vorstellen. Die Familie der $\eta_e$ ist genau die Bauanleitung für eine solche Widerspruchs-Kombination: Die Bedingungen $\eta_e(f(e)) = 0$ an jeder Kante und $\sum_{e \ni v} \eta_e = 0$ an jedem Knoten sorgen dafür, dass sich die linken Seiten wegheben. Die rechte Seite dieser Kombination ist $\sum_e \eta_e(d_e)$, und damit kein Widerspruch entsteht, muss sie null sein.

Dass dieses System immer lösbar ist, ist der letzte und cleverste Schritt (Lemma 2.2). Über die Dualräume reduziert sich die Lösbarkeit also auf eine einzige Bedingung: Jede Familie von Dualvektoren $\eta_e$, die $\eta_e(f(e)) = 0$ an jeder Kante und $\sum_{e \ni v} \eta_e = 0$ an jedem Knoten erfüllt, muss auch $\sum_e \eta_e(d_e) = 0$ erfüllen. Der Beweis rechnet diese Summe aus und erhält

$\sum_e \eta_e(d_e) = \sum_{v} \sum_{e \ni v} \mathbf{1}_{\eta_e \neq 0}.$

Rechts steht eine Summe über alle Knoten und ihre anliegenden Kanten. Dass sie modulo 2 verschwindet, ist der Kern von Lemma 2.2 und ergibt sich aus einer kurzen Rechnung an jedem einzelnen Knoten.

Warum die Rechnung lokal aufgeht

Erinnern wir uns an die lokalen Paare. Das an einem Knoten $v$ vorgeschlagene Paar einer Kante $e$ war $\{t_v + g_{v,e},\ t_v + g_{v,e} + f(e)\}$, wobei die Verschiebung so gewählt ist, dass nur die mittlere der drei Kanten beiträgt: $g_{v,a} = g_{v,c} = 0$ und $g_{v,b} = x$. Zerlegt man $d_e = g_{u,e} + g_{v,e}$ und sortiert die große Summe nach Knoten, so ist der Beitrag eines einzelnen Knotens gerade $\sum_{e \ni v} \eta_e(g_{v,e}) = \eta_b(x)$. Diesen Wert nennen wir $\lambda$.

Der Clou ist, dass $\lambda$ zugleich die Parität der Anzahl der nichtverschwindenden $\eta_e$ am Knoten ist. Die Bedingungen an die Dualvektoren, also $\eta_a + \eta_b + \eta_c = 0$ sowie $\eta_a(x) = 0$, $\eta_b(y) = 0$ und $\eta_c(z) = 0$ mit $z = x + y$, legen ihr Verhalten auf der von $x$ und $y$ aufgespannten Ebene fest. Es bleiben nur zwei Fälle:

• $\lambda = 0$: Dann verschwinden $\eta_a, \eta_b, \eta_c$ alle auf dieser Ebene. Die Linearformen, die auf einer zweidimensionalen Ebene verschwinden, bilden einen eindimensionalen Raum, enthalten außer der Null also genau einen Vektor. Jedes $\eta_e$ ist somit Null oder dieser eine Vektor, und weil ihre Summe Null ist, tritt er null- oder zweimal auf. Die Anzahl der nichtverschwindenden ist gerade.
• $\lambda = 1$: Dann nehmen $\eta_a, \eta_b, \eta_c$ auf der Basis $x, y$ die Werte $(0,1)$, $(1,0)$ und $(1,1)$ an, sind also alle drei ungleich Null. Die Anzahl ist ungerade.

Ein Zahlenbeispiel für den Fall $\lambda = 1$: Sei $x = 001$, $y = 010$ und damit $z = 011$. Wähle $\eta_a$ als „lies das mittlere Bit" (also $001 \mapsto 0$, $010 \mapsto 1$), $\eta_b$ als „lies das rechte Bit" ($001 \mapsto 1$, $010 \mapsto 0$) und $\eta_c = \eta_a + \eta_b$ als „lies das XOR beider Bits" ($011 \mapsto 0$). Dann ist $\eta_a(x) = 0$, $\eta_b(y) = 0$ und $\eta_c(z) = 0$, alle Bedingungen sind erfüllt, und alle drei Formen sind ungleich Null: eine ungerade Anzahl. Und tatsächlich ist $\lambda = \eta_b(x) = 1$. Für den Fall $\lambda = 0$ nimmt man umgekehrt für zwei der Formen „lies das linke Bit", das auf der Ebene aus $001$ und $010$ überall Null ist, und für die dritte die Nullform. Dann sind es zwei nichtverschwindende Formen, eine gerade Anzahl, und $\lambda = 0$.

In beiden Fällen ist $\lambda = \sum_{e \ni v} \mathbf{1}_{\eta_e \neq 0}$ modulo 2, und das ist die lokale Identität hinter der Gleichung von oben. Summiert über alle Knoten wird jede Kante mit $\eta_e \neq 0$ an ihren beiden Enden je einmal gezählt, die Gesamtsumme ist also gerade und modulo 2 gleich Null. Damit ist das System lösbar, die widerspruchsfreien Paare existieren, und mit Lemma 2.1 folgt die Doppelüberdeckung. Es ist derselbe Mechanismus wie in der Vermutung selbst: Weil jede Kante an genau zwei Enden zählt, geht die Parität auf, so wie am Ende jede Kante genau zweimal überdeckt wird.

Warum der Beweis als elementar gilt

Auffällig ist, wie wenig neue Maschinerie vorkommt. Die Zutaten sind alt: nowhere-zero flows und das benutzte 8-Fluss-Theorem stammen aus Arbeiten von Tutte, Kilpatrick und Jaeger, der Farbpaar-Trick von Szekeres (1973), der Rest ist lineare Algebra über $\mathbb{F}_2$, dem Körper mit zwei Elementen. Das spiegelt auch das Literaturverzeichnis des Papers: Alle zehn zitierten Arbeiten stammen aus den Jahren 1954 bis 1994. Neu ist allein die Kombination, vor allem die gelockerte Färbung aus Lemma 2.1 und das Paritätsargument, das die Konsistenzlücke schließt.

In diesem Sinn ist der Beweis elementar: Er verwendet ausschließlich seit Jahrzehnten bekannte Werkzeuge und hätte sich im Prinzip lange vor 2026 führen lassen.

Fazit

Der Beweis hat eine überschaubare Architektur: Reduktion auf brückenlose kubische Graphen, ein nowhere-zero flow über $(\mathbb{Z}/2)^3$ anstelle einer Dreifärbung, daraus mit Lemma 2.1 die Zwei-Elemente-Mengen, deren Verträglichkeit an den Kantenenden ein lineares System über $\mathbb{F}_2$ ist, und dessen Lösbarkeit ein Paritätsargument sichert. Es wird kein Fall durchgerechnet und nichts vom Computer verifiziert, es ist ein kurzer, klassischer Beweis, den eine KI gefunden hat. Ob er lückenlos ist, entscheidet die Prüfung durch die Fachwelt, die bei einem so lange offenen Problem eher Wochen als Stunden braucht.

Quellen

• Das Beweis-PDF von GPT-5.6 Sol Ultra (OpenAI)
• Der verwendete Prompt