A PROOF OF THE CYCLE DOUBLE COVER CONJECTURE
OPENAI
Abstract. Seymour, which asserts that every bridgeless undirected graph has a collection of cycles which covers every
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-edgecolourable 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Γ = F³2such 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
$$ \Gamma=\mathbb{F}_{2}^{3} $$
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).
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. If A is an abelian group, an A-flowis a map f : E(G) →A for which,
$$ f:E(G)\to A $$
if f (e) ̸= 0for every edge. For an integer k≥ 2, aninteger k-flowis an integer-valued flow ϕ satisfying
$$ f(e)\stackrel{\circ}{\neq}0 $$
LetΓ = F³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.
setP e ⊆Γsuch that, for everyv∈V(G)ands∈Γ,
$$ \phi $$
∈{0,2}.(1)
$$ \Gamma=\mathbb{F}_{2}^{3}, $$
$$ P_{e}\subseteq\Gamma $$
$$ \left|{e\ni v:s\in P_{e}}\right|\in{0,2}. $$
$$ 0<|\phi(e)|<k $$
ThenGhas a cycle double cover.
A proper3-edge-colouring is an assignment of this form. For distinct e₁,e₂ ∈ Γ, assign {0,e₁}, {0,e₂}, and{e₁,e₂}to the red, blue, and green edges, respectively. At each vertex each of0,e₁,e₂ then appears twice. Thus Lemma 2.1 can be seen as a suitably relaxed variant of a proper3-edge-colouring. 1
$$ v\in V(G) $$
$$ {0,e_{1}},,{0,e_{2}} $$
$$ 0,e_{1},e_{2} $$
Proof. For s∈ Γ, let Ms= {e : s∈Pe}. By (1), every vertex has degree zero or two in Ms, so Msis a disjoint union of cycles. Every edge belongs to exactly two of the Ms, since Pehas two elements. The cycle components of all theMs, taken with multiplicity, form a cycle double cover.□
$$ M_{s}=\left{e:s\in P_{e}\right} $$
$$ s\in\Gamma $$
$$ M_{s}. $$
$$ M_{s} $$
$$ M_{s} $$
$$ M_{s} $$
It remains to construct the sets Pe. Fix a nowhere-zeroΓ-flow f. At each vertex v, locally order the incident edges as a,b,c and 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
$$ P_{e} $$
$$ x=f(a),y=f(b) $$
$$ a,b,c $$
$$ z=f(c) $$
$$ x+y+z=0 $$
$$ g_{v,a}=0,\qquad g_{v,b}=x,\qquad g_{v,c}=0. $$
= 0.(2)
For anyt∈Γ, the three local sets
$$ t\in\Gamma $$
+f(e)}(e∋v)(3)
$$ {t + g _ {v, e}, t + g _ {v, e} + f (e) } \quad (e \ni v) $$
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 d = g + g. For any p∈ Γ, {A,A + p} = {B,B + p} precisely when A + B∈{0,p}.
$$ \big{t,t+x\big},,\big{t+x,t+z\big} $$
$$ {t,t+z} $$
For e = uv, put de= gu,e+ gv,e. For any p∈ Γ, {A,A + p} = {B,B + p} precisely when A + B∈{0,p}. Apply this with A = tu+ gu,e, B = tv+ gv,e, and p = f (e). Then A + B = tu+ tv+ de, and the choice of ϵe∈F₂ records whether this vector is0or f (e). Thus the local sets in (3) agree across every edge precisely when there aretv∈Γandϵe∈F₂ satisfying
$$ \ !,p p\in\Gamma,\left{A,A!+!p\right}=\left{B,B!+!p\right}, $$
$$ e=u v $$
$$ d_{e}=g_{u,e}+g_{v,e} $$
$$ A+B\in{0,p} $$
$$ A=t_{u}+g_{u,e},,B=t_{v}+g_{v,e} $$
$$ A+B=t_{u}+t_{v}+d_{e} $$
$$ \epsilon_{e}\in\mathbb{F}_{2} $$
$$ t_{v}\in\Gamma $$
$$ \epsilon_{e}\in\mathbb{F}_{2} $$
$$ t _ {u} + t _ {v} + \epsilon_ {e} f (e) = d _ {e} \quad (e = u v). $$
(e=uv).(4)
Lemma 2.2.The system(4)has a solution.
Assuming the lemma, define Pe= {tv+ gv,e,tv+ gv,e+ f (e)} using either endpoint v of e. Equation (4) makes this independent of the endpoint, and f (e) ̸= 0makes the two elements distinct. The local calculation above gives (1); Lemma 2.1 proves the theorem.
$$ P_{e}=\left{t_{v}+g_{v,e},t_{v}+g_{v,e}+f(e)\right} $$
$$ f(e)\neq0 $$
Proof of Lemma 2.2.Let
$$ L:\Gamma^{V(G)}\oplus\mathbb{F} {2}^{E(G)}\longrightarrow\Gamma^{E(G)},\qquad L(t,\epsilon){e}=t_{u}+t_{v}+\epsilon_{e}f(e)\quad(e=u v). $$
∗ Thus (4) asks whether d = (de)ebelongs to imL. LetΓ be the dual vector space ofΓ; thus an element of ∗ E(G) Γ is an F₂-linear map fromΓto F₂. We may write a dual vector toΓ 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 P imLalso satisfies ηe(de) = 0. Now e !
$$ d=(d_{e})_{e} $$
$$ \Gamma, $$
$$ \Gamma^{*} $$
$$ \Gamma^{*} $$
$$ \mathbb{F}_{2} $$
$$ \mathbb{F}_{2} $$
$$ \eta=(\eta_{e})_{e\in E(G)} $$
$$ d\in\operatorname{i m}L $$
$$ \sum_{e}\eta_{e}\big(L(t,\epsilon) {e}\big)=\sum{v}\left(\sum_{e\ni v}\eta_{e}\right)(t_{v})+\sum_{e}\epsilon_{e}\eta_{e}(f(e)). $$
Since thetvandϵemay be chosen independently, this vanishes for every(t,ϵ)precisely when X
Fixvand retain the notationa,b,c,x,y,z. The conditions (5) become
$$ \eta_{e}\in\Gamma^{*} $$
$$ \sum_{e}\eta_{e}(d_{e})=0 $$
(z) = 0.(7)
$$ \eta_{a}+\eta_{b}+\eta_{c}=0,\qquad\eta_{a}(x)=0,\qquad\eta_{b}(y)=0,\qquad\eta_{c}(z)=0. $$
Setλ=η b (x). Sinceη c =η a +η b andz=x+y,
$$ 0=\eta_{c}(z)=\eta_{a}(y)+\eta_{b}(x) $$
$$ z=x+y, $$
where we used ηa(x) = ηb(y) = 0. Hence ηa(y) = λ. By (2), only the edge b contributes at v, and therefore X
$$ \eta_{a}(x)=\eta_{b}(y)=0. $$
$$ \upsilon, $$
$$ \sum_{e\ni v}\eta_{e}(g_{v,e})=\eta_{b}(x)=\lambda. $$
We next interpret λ. If λ = 0, all three dual vectors vanish on W = ⟨x,y⟩. There is a unique nonzero dual vector which vanishes on this two-dimensional space, so each of ηa,ηb,ηcis 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,y are(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η̸=0for the corresponding bit, X X
$$ \lambda=0 $$
$$ W=\langle x,y\rangle $$
$$ \eta_{a},\eta_{b},\eta_{c} $$
$$ x,y $$
$$ \lambda=1 $$
$$ {\eta_{a},\eta_{b},\eta_{c}} $$
$$ \mathbf{1}_{\eta\neq0} $$
$$ \sum_{e\ni v}\eta_{e}(g_{v,e})=\sum_{e\ni v}\mathbf{1} {\eta{e}\neq0}. $$
.(9)
Finally, for e = uv, the definition de= gu,e+ gv,eand linearity of ηegive η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 X X X X
$$ e=u v $$
$$ \ {e}=g{u,e}+g_{v,e}\ , $$
$$ \eta_{e} $$
$$ \eta_{e}(d_{e})=\eta_{e}(g_{u,e})+\eta_{e}(g_{v,e}) $$
$$ \sum_{e}\eta_{e}(d_{e})=\sum_{v}\sum_{e\ni v}\eta_{e}(g_{v,e})=\sum_{v}\sum_{e\ni v}\mathbf{1} {\eta{e}\neq0} $$
P Each edge with ηe̸= 0occurs twice in the last sum, once at each endpoint. Hence it equals2 1ηe̸=0= 0 e inF₂. This proves (6); by the duality criterion above,d∈imL, so (4) has a solution.□
$$ \eta_{e}\neq0 $$
$$ 2\sum_{e}\mathbf{1} {\eta{e}\neq0}=0 $$
$$ \mathbb{F}_{2} $$
$$ d\in\operatorname{i m}L, $$
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.
[10] W. T. Tutte, personal correspondence with H. Fleischner, July 22, 1987.
