OPENAI 摘要。我们证明了由 Tutte、Itai 和 Rodeh、Szekeres 以及 Seymour 提出的圈双覆盖猜想，该猜想断言：每个无桥无向图都存在一个圈的集合，使得每条边恰好被覆盖两次。
- 引言
图的圈双覆盖是一个圈的多重集，其中每条边恰好出现两次。该猜想由 Tutte [10]、Itai 和 Rodeh [2]、Szekeres [8] 以及 Seymour [6] 提出。更多背景信息可参见 Jaeger 的综述 [3]。
定理 1.1。每个有限无桥无向图都存在一个圈双覆盖。
在部分成果中，Jaeger 指出该猜想对平面图成立，方法是取各块的面的边界圈 [3, 第 2.1 节和第 3.1 节]；Szekeres 指出该猜想对 3-边可着色的三次图成立，方法是取三个颜色类两两并集 [8, 第 367 页]；Alspach、Goddyn 和 Zhang 证明了该猜想对不含 Petersen 子图的无桥图成立 [1]。证明过程首先利用（按标准做法）只需考虑三次图即可。然后，利用 8-流定理和 Tutte 的一个结果，我们得到一种用 Γ = F₃² 的非零元素对边进行标记的方式，使得每个顶点处的和为零。关键化简在于，将这种标记转化为用 Γ 中两个元素的集合对边进行标记，使得每个 Γ 中的元素在给定顶点处出现零次或两次。这一化简最终归结为一个基础的线性代数论证。
AI 使用声明。本笔记中的证明完全归功于 GPT 5.6 Sol Ultra，并使用 Codex（配合 GPT 5.6 Sol）撰写。2. 猜想的证明
我们允许平行边，并将两条平行边视为一个圈。根据 Jaeger [3, 命题 4]，只需处理无环三次图即可。事实上，Jaeger 指出，一个最小的反例必定不是
3-边可着色的——也就是说，它必定是一个 snark——我们将在下文回到这一观察。固定图的一个定向。若 A 是一个阿贝尔群，则一个 A-流是一个映射 f : E(G) → A，使得在每个顶点处，出边上的和等于入边上的和。它是处处非零的。
如果对于每条边 e 都有 f(e) ≠ 0。对于整数 k ≥ 2，一个整数 k-流是一个取整数值的流 ϕ，满足
每条边上都有 0 < |ϕ(e)| < k。设 Γ = F32，采用加法记号。Kilpatrick 和 Jaeger 独立证明了每个无桥图都存在一个无处为零的 Γ-流 [5, 4]，或者等价地，根据 Tutte 的群流定理，存在一个无处为零的 8-流 [9]。（Seymour 后来的 6-流定理 [7] 更强，但此处不需要。）我们现在将这个 Γ-流转化为一个圈双覆盖；这一约简仅要求底层图 G 是无环的三次图。
引理 2.1。设 G 是一个无环的三次多重图。假设每条边 e 都被赋予一个二元子集 Pe ⊆ Γ，使得对于每个 v ∈ V(G) 和 s ∈ Γ，
{e ∋ v : s ∈ Pe} ∈ {0, 2}。 (1)
那么 G 存在一个圈双覆盖。
一个正常的 3-边染色就是这种形式的一种赋值。对于不同的 e1, e2 ∈ Γ，分别将 {0, e1}、{0, e2} 和 {e1, e2} 赋给红色、蓝色和绿色的边。在每个顶点处，0、e1、e2 各出现两次。因此，引理 2.1 可以看作是正常 3-边染色的一种适当放宽的变体。
证明。对于 s ∈ Γ，令 Ms = {e : s ∈ Pe}。由 (1) 可知，每个顶点在 Ms 中的度数要么为 0 要么为 2，因此 Ms 是一些不交圈的并集。每条边恰好属于两个 Ms，因为 Pe 有两个元素。所有 Ms 的圈分量（计重数）构成了一个圈双覆盖。□
接下来需要构造集合 Pe。固定一个无处为零的 Γ-流 f。在每个顶点 v 处，将关联的边局部排序为 a、b、c，并记 x = f(a)、y = f(b)、z = f(c)。由于 Γ 的特征为 2，流方程为 x + y + z = 0，因此 z = x + y；此外 x 和 y 不相等。定义
gv,a = 0，gv,b = x，gv,c = 0。 (2) 对于任意 t ∈ Γ，这三个局部集合
{t + gv,e , t + gv,e + f (e)} (e ∋ v) (3) 是 {t, t + x}, {t + x, t + z} 和 {t, t + z}。因此每个向量出现在其中零个或两个集合中。这种赋值在局部成立，但一条边的两个端点未必会赋予它相同的集合。对于 e = uv，令 de = gu,e + gv,e。对于任意 p ∈ Γ，当且仅当 A + B ∈ {0, p} 时，{A, A + p} = {B, B + p}。将此应用于 A = tu + gu,e，B = tv + gv,e，以及 p = f (e)。那么 A + B = tu + tv + de，而 ϵe ∈ F2 的选择记录了该向量是 0 还是 f (e)。因此，当且仅当存在 tv ∈ Γ 和 ϵe ∈ F2 满足以下条件时，(3) 中的局部集合在每条边上一致：
tu + tv + ϵef (e) = de (e = uv)。 (4)
引理 2.2。方程组 (4) 有解。
假设该引理成立，则使用 e 的任一端点 v 定义 Pe = {tv + gv,e , tv + gv,e + f (e)}。方程 (4) 使得该定义与端点无关，而 f (e) ≠ 0 使得两个元素不同。上述局部计算给出了 (1)；引理 2.1 证明了该定理。
引理 2.2 的证明。令
L : Γ V(G) ⊕ F2E(G) → ΓE(G)，L(t, ϵ)e = tu + tv + ϵef (e) (e = uv)。
因此 (4) 询问 d = (de)e 是否属于 im L。令 Γ* 为 Γ 的对偶向量空间；因此 Γ* 的一个元素是
从 Γ 到 F2 的 F2-线性映射。我们可以将 ΓE(G) 的一个对偶向量写为族 η = (ηe)e∈E(G)，
其中 ηe ∈ Γ*。通过对偶化，d ∈ im L 当且仅当每个在 im L 上取值为零的此类族也满足
Σ ηe(de) = 0。现在
Σ ηe
L(t, ϵ)e
= Σ
(Σ
ηe
)
(tv) + Σ
ϵeηe(f (e))。
由于 tv 和 ϵe 可以独立选择，当且仅当以下条件成立时，该式对每个 (t, ϵ) 都为零：
ηe(f (e)) = 0 (e ∈ E(G))，Σ
ηe = 0 (v ∈ V(G))。 (5) 因此，只需证明每个满足 (5) 的族也满足
Σ
ηe(de) = 0。 (6) 固定 v 并保留记号 a, b, c, x, y, z。条件 (5) 变为
ηa + ηb + ηc = 0，ηa(x) = 0，ηb(y) = 0，ηc(z) = 0。 (7) 令 λ = ηb(x)。由于 ηc = ηa + ηb 且 z = x + y，
0 = ηc(z) = ηa(y) + ηb(x)，
这里我们使用了 ηa(x) = ηb(y) = 0。因此 ηa(y) = λ。由 (2)，在 v 处只有边 b 有贡献，因此
Σ
ηe(gv,e) = ηb(x) = λ。 (8) 循环双覆盖猜想的一个证明 3
X
ηe(gv,e ) = ηb(x) = λ. (8) A PROOF OF THE CYCLE DOUBLE COVER CONJECTURE 3
接下来我们解释 λ。若 λ = 0，则三个对偶向量在 W = ⟨x, y⟩ 上均消失。存在唯一一个非零对偶向量在该二维空间上消失，因此 ηa、ηb、ηc 要么为零，要么就是这个向量。由于它们的和为零，该非零向量出现零次或两次。若 λ = 1，它们在有序基 x、y 上的取值分别为 (0, 1)、(1, 0) 和 (1, 1)，因此三者均非零。无论哪种情况，λ 都是 {ηa、ηb、ηc} 中非零成员个数的奇偶性。因此，将 1η̸ =0 记为对应比特位，
X
ηe(gv,e ) = X
e∋v
1ηe̸ =0 。 (9) 最后，对于 e = uv，由定义 de = gu,e + gv,e 以及 ηe 的线性性可得 ηe(de) = ηe(gu,e ) + ηe(gv,e )。对所有边求和，然后在每个顶点处将两个端点项合并，(9) 式给出
X
e
ηe(de) = X
v
X
e∋v
ηe(gv,e ) = X
v
X
e∋v
1ηe̸ =0
每个满足 ηe̸ = 0 的边在最后一项求和中出现两次，每个端点各一次。因此该项等于 2 P
e
1ηe̸ =0 = 0
在 F2 中。这就证明了 (6) 式；根据上述对偶准则，d ∈ im L，因此 (4) 式有解。□
参考文献
[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 和 M. Rodeh，《用环覆盖图》，载于《自动机、语言与编程》（G. Ausiello 与 C. Böhm 编），《计算机科学讲义》第 62 卷，Springer，1978 年，第 289–299 页。 [3] F. Jaeger，《环双覆盖猜想综述》，载于《图中的环》，《北荷兰数学研究》第 115 卷，北荷兰出版社，1985 年，第 1–12 页。 [4] F. Jaeger，《关于多重图中的无处零流》，载于《第五届英国组合数学会议论文集》，《组合数学》第 XV 卷，Utilitas Math.，1976 年，第 373–378 页。 [5] P. A. Kilpatrick，《Tutte 第一颜色-环猜想》，硕士论文，开普敦大学，1975 年。 [6] P. D. Seymour，《环的和》，载于《图论与相关主题》，Academic Press，1979 年，第 341–355 页。 [7] P. D. Seymour，《无处零 6-流》，《组合理论杂志 B 辑》第 30 卷（1981 年），第 130–135 页。 [8] G. Szekeres，《三次图的多面体分解》，《澳大利亚数学会通报》第 8 卷（1973 年），第 367–387 页。 [9] W. T. Tutte，《对色多项式理论的贡献》，《加拿大数学杂志》第 6 卷（1954 年），第 80–91 页。 [10] W. T. Tutte，与 H. Fleischner 的个人通信，1987 年 7 月 22 日。
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.
- 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 Γ = F32 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 Γ = F32, 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, e 2 ∈ Γ, assign {0, e 1}, {0, e 2},and {e1, e 2} to the red, blue, and green edges, respectively. At each vertex each of 0, e 1, e 2 then appears twice. Thus Lemma 2.1 can be seen as a suitably relaxed variant of a proper 3-edge-colouring.
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 , t v + 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(de) = 0 . Now
X
ηe
L(t, ϵ )e
= X
X
ηe
!
(tv) + X
ϵ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 = 0 (v ∈ V (G)) . (5) Consequently, it suffices to prove that every family satisfying (5) also satisfies
X
η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(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(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.