OPENAI 摘要。我们证明了由 Tutte、Itai 和 Rodeh、Szekeres 以及 Seymour 提出的圈双覆盖猜想，该猜想断言：每个无桥无向图都存在一个圈的集合，使得每条边恰好被覆盖两次。

1. 引言

图的圈双覆盖是一个圈的多重集，其中每条边恰好出现两次。该猜想由 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 日。