A proof of the cycle double cover conjecture by OpenAI: An exposition
2026-07-17
I have written an exposition of a proof of the cycle double cover conjecture announced by OpenAI in July 11, 2026, while preparing a talk at the Discrete Math Seminar at IBS given at July 16, 2026:
The cycle double cover conjecture states that every bridgeless graph has a list of cycles in which every edge appears exactly twice. Since every Eulerian graph can be decomposed into edge-disjoint cycles, one can equivalently ask for a list of Eulerian subgraphs with the same property. The bridgeless assumption is necessary because a bridge belongs to no cycle.
The exposition follows a proof by reducing the problem to a particularly structured case. A minimal counterexample must be cubic and 3-edge-connected. The reduction uses a splitting lemma of Fleischner: a vertex of degree at least four can be replaced by a smaller 2-edge-connected graph, and a cycle double cover of the smaller graph can then be lifted back. A 2-edge-cut can similarly be handled by contraction and lifting. Thus it is enough to consider cubic 3-edge-connected graphs.
The next ingredient is the existence of three spanning trees with no edge contained in all three. This follows from the Tutte–Nash-Williams theorem on edge-disjoint spanning trees, applied after adding a parallel copy of every edge. From these spanning trees, one constructs a nowhere-zero flow with values in $\mathbb{F}_2^3$. The construction is elementary: for each spanning tree, take a suitable Eulerian edge set containing all edges outside the tree, and use the three characteristic functions as the coordinates of the flow.
The core of the argument converts this flow into a cycle double cover. At each edge, the flow determines a two-element subset of $\mathbb{F}_2^3$. If these two-element can be chosen consistenly while satisfying an evenness condition at every vertex, then the edges carrying any fixed label form an Eulerian subgraph, and all such subgraphs together give a cycle double cover.
The remaining issue is to choose the labels consistently. For a cubic graph, the proof introduces vectors at the vertices and asks that the sum of the vectors at the ends of each edge lie in a prescribed affine one-dimensional subspace. An elementary linear-algebra criterion reduces the consistency of this system to checking certain orthogonality relations. The key identity is the familiar fact that the column space of a matrix is the orthogonal complement of its left nullspace. Over $\mathbb{F}_2$, a local calculation at each cubic vertex makes the required global obstruction vanish, so the vertex vectors exist. The flow-lifting lemma then produces the desired cycle double cover.
Combining the minimal-counterexample reduction with the cubic case proves the conjecture for every bridgeless graph.
The paper also discusses related questions. The proof gives an 8-cycle double cover, while the stronger 5-cycle double cover conjecture remains open. Other topics include orientable cycle double covers, their connection with nowhere-zero flows, and the Berge–Fulkerson conjecture on perfect matchings.
The exposition modifies the announced proof in two main ways: the two values assigned to each edge of $\mathbb{F}_2^3$ are chosen symmetrically, and the linear-algebra part is presented without dual vector spaces. Parts of the revision were carried out with GPT 5.6 under my guidance.
The video of my talk on July 16, 2026 can be found at YouTube:
Comments