A PROOF OF THE CYCLE DOUBLE COVER CONJECTURE
OPENAI
Abstract. We prove the cycle double cover conjecture, posed by Tutte, Itai and Rodeh, Szekeres, and
Seymour, which asserts that every bridgeless undirected graph has a collection of cycles which covers every
edge exactly twice.
1.Introduction
Acycle double coverof a graph is a multiset of cycles in which every edge occurs exactly twice. The
conjecture was posed by Tutte [10], Itai and Rodeh [2], Szekeres [8], and Seymour [6]. See the survey of
Jaeger [3] for further background.
Theorem 1.1.Every finite bridgeless undirected graph has a cycle double cover.
Among partial results, Jaeger observed that the conjecture holds for planar graphs by taking the
facial boundary cycles of their blocks [3, Sections 2.1 and 3.1], Szekeres observed that it holds for3-edge-
colourable cubic graphs by taking the three unions of pairs of colour classes [8, p. 367], and Alspach,
Goddyn, and Zhang proved it for bridgeless graphs with no Petersen subdivision [1]. The proof proceeds
by first using that it suffices (as is standard) to consider cubic graphs. Then, using the8-flow theorem
and a result of Tutte, we have a labeling of the edges by nonzero elements ofΓ =F3
2 such that the sum at
each vertex is zero. The key reduction is then to convert this labeling into a labeling of the edges by sets
of two elements inΓsuch that each element ofΓappears either zero or twice next to a given vertex. This
reduction eventually reduces to an elementary linear algebra argument.
Statement of AI use.The proof in this note is entirely due to GPT 5.6 Sol Ultra and the writeup with
Codex (with GPT 5.6 Sol).
2.Proof of the conjecture
We allow parallel edges and regard two parallel edges as a cycle. By Jaeger [3, Proposition 4], it suffices
to treat loopless cubic graphs. In fact, Jaeger observed that a minimum counterexample must fail to be
3-edge-colourable—that is, it must be a snark—and we return to this observation below.
Fix an orientation of a graph. IfA is an abelian group, anA-flowis a map f : E(G) →A for which,
at every vertex, the sum on edges directed out equals the sum on edges directed in. It isnowhere-zero
if f (e) ̸= 0for every edge. For an integerk≥ 2, aninteger k-flowis an integer-valued flow ϕ satisfying
0<|ϕ(e)|< kon every edge.
LetΓ = F3
2, written additively. Kilpatrick and Jaeger independently proved that every bridgeless graph
has a nowhere-zeroΓ-flow [5, 4], or, equivalently by Tutte’s group-flow theorem, a nowhere-zero8-flow [9].
(Seymour’s later6-flow theorem [7] is stronger, but unnecessary here.) We now massage thisΓ-flow into a
cycle double cover; this reduction only requires that the underlying graphGis loopless and cubic.
Lemma 2.1.Let G be a loopless cubic multigraph. Suppose that every edgee is assigned a two-element
setP e ⊆Γsuch that, for everyv∈V(G)ands∈Γ,{e∋v:s∈P e}
 ∈ {0,2}.(1)
ThenGhas a cycle double cover.
A proper3-edge-colouring is an assignment of this form. For distincte1, e2 ∈ Γ, assign {0, e1}, {0, e2},
and{e 1, e2}to the red, blue, and green edges, respectively. At each vertex each of0, e1, e2 then appears
twice. Thus Lemma 2.1 can be seen as a suitably relaxed variant of a proper3-edge-colouring.
1
2 OPENAI
Proof. For s∈ Γ, let Ms = {e : s∈P e}. By (1), every vertex has degree zero or two inMs, so Ms is a
disjoint union of cycles. Every edge belongs to exactly two of theMs, since Pe has two elements. The
cycle components of all theMs, taken with multiplicity, form a cycle double cover.□
It remains to construct the setsPe. Fix a nowhere-zeroΓ-flow f. At each vertexv, locally order the
incident edges asa, b, cand write x = f (a), y = f (b), and z = f (c). SinceΓhas characteristic two, the
flow equation isx+y+z= 0, soz=x+y; moreoverxandyare distinct. Define
gv,a = 0, g v,b =x, g v,c = 0.(2)
For anyt∈Γ, the three local sets
{t+g v,e, t+gv,e +f(e)}(e∋v)(3)
are {t, t+ x}, {t + x, t+ z}, and {t, t+ z}. Hence every vector occurs in zero or two of them. This
assignment works locally, but the two ends of an edge need not assign it the same set.
For e = uv, put de = gu,e + gv,e. For anyp∈ Γ, {A, A+ p} = {B, B+ p} precisely when A + B∈ {0, p}.
Apply this withA = tu + gu,e, B = tv + gv,e, and p = f (e). Then A + B = tu + tv + de, and the choice
of ϵe ∈F 2 records whether this vector is0or f (e). Thus the local sets in(3) agree across every edge
precisely when there aretv ∈Γandϵ e ∈F 2 satisfying
tu +t v +ϵ ef(e) =d e (e=uv).(4)
Lemma 2.2.The system(4)has a solution.
Assuming the lemma, definePe = {tv + gv,e, tv + gv,e + f (e)} using either endpointv of e. Equation (4)
makes this independent of the endpoint, andf (e) ̸= 0makes the two elements distinct. The local
calculation above gives (1); Lemma 2.1 proves the theorem.
Proof of Lemma 2.2.Let
L: Γ V(G) ⊕F E(G)
2 − →ΓE(G), L(t, ϵ) e =t u +t v +ϵ ef(e) (e=uv).
Thus (4) asks whether d = (de)e belongs to imL. LetΓ ∗ be the dual vector space ofΓ; thus an element of
Γ∗ is an F2-linear map fromΓto F2. We may write a dual vector toΓE(G) as a familyη = (ηe)e∈E(G)
with ηe ∈ Γ∗. By taking duals,d∈imL if and only if every such family which takes the value zero on
imLalso satisfies P
e ηe(de) = 0. Now
X
e
ηe
 
L(t, ϵ)e

=
X
v
 X
e∋v
ηe
!
(tv) +
X
e
ϵeηe(f(e)).
Since thet v andϵ e may be chosen independently, this vanishes for every(t, ϵ)precisely when
ηe(f(e)) = 0 (e∈E(G)),
X
e∋v
ηe = 0 (v∈V(G)).(5)
Consequently, it suffices to prove that every family satisfying (5) also satisfies
X
e
ηe(de) = 0.(6)
Fixvand retain the notationa, b, c, x, y, z. The conditions (5) become
ηa +η b +η c = 0, η a(x) = 0, η b(y) = 0, η c(z) = 0.(7)
Setλ=η b(x). Sinceη c =η a +η b andz=x+y,
0 =η c(z) =η a(y) +η b(x),
where we usedηa(x) = ηb(y) = 0. Hence ηa(y) = λ. By (2), only the edgeb contributes atv, and therefore
X
e∋v
ηe(gv,e) =η b(x) =λ.(8)
A PROOF OF THE CYCLE DOUBLE COVER CONJECTURE 3
We next interpretλ. If λ = 0, all three dual vectors vanish onW = ⟨x, y⟩. There is a unique nonzero
dual vector which vanishes on this two-dimensional space, so each ofηa, ηb, ηc is either zero or this vector.
Since their sum is zero, the nonzero vector occurs zero or two times. Ifλ = 1, their values on the ordered
basis x, yare(0 , 1),(1 , 0), and(1 , 1), so all three are nonzero. In either case,λ is the parity of the number
of nonzero members of{ηa, ηb, ηc}. Thus, writing1 η̸=0 for the corresponding bit,
X
e∋v
ηe(gv,e) =
X
e∋v
1ηe̸=0.(9)
Finally, fore = uv, the definitionde = gu,e + gv,e and linearity ofηe give ηe(de) = ηe(gu,e) + ηe(gv,e).
Summing over all edges and then grouping the two endpoint terms at each vertex, (9) gives
X
e
ηe(de) =
X
v
X
e∋v
ηe(gv,e) =
X
v
X
e∋v
1ηe̸=0
Each edge withηe ̸= 0occurs twice in the last sum, once at each endpoint. Hence it equals2P
e 1ηe̸=0 = 0
inF 2. This proves (6); by the duality criterion above,d∈imL, so (4) has a solution.□
References
[1] B. Alspach, L. A. Goddyn, and C.-Q. Zhang,Graphs with the circuit cover property, Trans. Amer. Math. Soc.344
(1994), 131–154.
[2] A. Itai and M. Rodeh,Covering a graph by circuits, inAutomata, Languages and Programming(G. Ausiello and C.
Böhm, eds.), Lecture Notes in Comput. Sci.62, Springer, 1978, 289–299.
[3] F. Jaeger,A survey of the cycle double cover conjecture, inCycles in Graphs, North-Holland Math. Stud.115,
North-Holland, 1985, 1–12.
[4] F. Jaeger,On nowhere-zero flows in multigraphs, inProceedings of the Fifth British Combinatorial Conference, Congr.
Numer.XV, Utilitas Math., 1976, 373–378.
[5] P. A. Kilpatrick,Tutte’s first colour-cycle conjecture, M.Sc. thesis, University of Cape Town, 1975.
[6] P. D. Seymour,Sums of circuits, inGraph Theory and Related Topics, Academic Press, 1979, 341–355.
[7] P. D. Seymour,Nowhere-zero6-flows, J. Combin. Theory Ser. B30(1981), 130–135.
[8] G. Szekeres,Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc.8(1973), 367–387.
[9] W. T. Tutte,A contribution to the theory of chromatic polynomials, Canad. J. Math.6(1954), 80–91.
[10] W. T. Tutte, personal correspondence with H. Fleischner, July 22, 1987.