GPT-5.6 Sol Ultra produces proof of the Cycle Double Cover Conjecture [pdf]

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 A cycle double cover of 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 for 3-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 the 8-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. If A is an abelian group, an A-flow is 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 is nowhere-zero if f (e)̸ = 0 for every edge. For an integer k ≥ 2, an integer k-flow is an integer-valued flow ϕ satisfying 0 < |ϕ(e)| < k on 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-zero 8-flow [9]. (Seymour’s later 6-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 graph G is loopless and cubic. Lemma 2.1. Let G be a loopless cubic multigraph. Suppose that every edge e is assigned a two-element set Pe ⊆ Γ such that, for every v ∈ V (G) and s ∈ Γ, {e ∋ v : s ∈ Pe} ∈ {0, 2}. (1) Then G has a cycle double cover. A proper 3-edge-colouring is an assignment of this form. For distinct e1, e2 ∈ Γ, assign {0, e1}, {0, e2}, and {e1, e2} to the red, blue, and green edges, respectively. At each vertex each of 0, e1, e2 then appears twice. Thus Lemma 2.1 can be seen as a suitably relaxed variant of a proper 3-edge-colouring. 1 2 OPENAI Proof. For s ∈ Γ, let Ms = {e : s ∈ Pe}. By (1), every vertex has degree zero or two in Ms, so Ms is a disjoint union of cycles. Every edge belongs to exactly two of the Ms, since Pe has two elements. The cycle components of all the Ms, taken with multiplicity, form a cycle double cover. □ 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 is x + y + z = 0, so z = x + y; moreover x and y are distinct. Define gv,a = 0, gv,b = x, gv,c = 0. (2) For any t ∈ Γ, the three local sets {t + gv,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 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 ∈ F2 records whether this vector is 0 or f (e). Thus the local sets in (3) agree across every edge precisely when there are tv ∈ Γ and ϵe ∈ F2 satisfying tu + tv + ϵef (e) = de (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)̸ = 0 makes 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) ⊕ FE(G) 2 −→ ΓE(G), L(t, ϵ)e = tu + tv + ϵef (e) (e = uv).

Thus (4) asks whether d = (de)e belongs to im L. 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 ∈ im L if and only if every such family which takes the value zero on im L also 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 the tv 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) Fix v and retain the notation a, 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 and z = x + y, 0 = ηc(z) = ηa(y) + ηb(x), where we used ηa(x) = ηb(y) = 0. Hence ηa(y) = λ. By (2), only the edge b contributes at v, 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 on W = ⟨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, 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, writing 1η̸ =0 for the corresponding bit, X e∋v ηe(gv,e) = X e∋v 1ηe̸ =0. (9) Finally, for e = uv, the definition de = 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̸ = 0 occurs twice in the last sum, once at each endpoint. Hence it equals 2 P e 1ηe̸ =0 = 0 in F2. This proves (6); by the duality criterion above, d ∈ im L, 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, in Automata, 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, in Cycles in Graphs, North-Holland Math. Stud. 115, North-Holland, 1985, 1–12. [

4] F. Jaeger, On nowhere-zero flows in multigraphs, in Proceedings 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, in Graph Theory and Related Topics, Academic Press, 1979, 341–355. [7] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (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.