2026-08-11
GPT-5.6 生成的证明搞定 2014 年的 Imbalance 猜想：凡每条边两端度数都不同的图，其边失衡度多重集必为某个图的度数序列。
Albertson 1997 年用「所有边的失衡度之和」来度量一张图有多不规则，失衡度就是一条边两端顶点度数之差的绝对值。Kozerenko 和 Skochko 2014 年换了个角度：不看总和，看每条边失衡度凑成的多重集 MG。他们猜想，只要图里每条边的失衡度都大于 0（即没有两端度数相同的边），MG 就是 graphic 的，能当某张图的度数序列。Kozerenko 和 Serdiuk 2023 年把这条在 12 阶以内的图上做了穷举验证，但一般情形的证明一直缺。这篇就是补这个证明。
目标是套上 Erdős–Gallai 定理。这条定理说：一串非负整数排成非增序列后，能当某个简单图的度数序列，当且仅当总和为偶、且对每个前缀 k 满足一组不等式（前 k 大的数之和，不超过 k(k−1) 加上后面每个数与 k 取 min 之和）。于是全部工作归约成：把 MG 排成非增序列 (x₁≥…≥xm)，证明每一条 Erdős–Gallai 不等式都成立，外加总和为偶。
核心是一件新工具 Lemma 3.1（截断失衡下界）：若至少有 k 条边失衡度不小于 k，记 D 为最大失衡度，则截断和 Tk = Σe min{k, δ(e)} 不小于 k(D+1)。它的证法是删掉那条最大失衡边的高度数端点 v，把剩下的边分成「与 v 相邻的」和「其余的」两堆分别放缩，再分 h≥k 与 h<k 两种情形算清。这是全篇唯一需要真算计的地方，其余都是套用。
主定理对 k 归纳，分两种情形。若 xk ≥ k（前 k 个失衡度都不小于 k），直接用引理得 Tk ≥ k(D+1)，再因每个 xi ≤ D 凑出 Erdős–Gallai 不等式。若 xk < k，则从第 k 项起 min{k, xi}=xi，可推出相邻两项的 slack 满足 Φk − Φ{k−1} = 2(k−1−xk) ≥ 0。最后一段奇偶论证收尾：每条边失衡度 |d(u)−d(v)| 在模 2 下等于 d(u)+d(v)，对所有边求和正好等于 Σv d(v)²，而后者模 2 等于 Σv d(v) = 2|E| ≡ 0，所以总和为偶。Erdős–Gallai 条件一齐满足，MG 就是图序列。
和反例那篇不同，这篇是纯分析证明，没有可复算的机器核验。证明链没有逐行重推，只能转述结构和采信作者；它由作者据 GPT-5.6 的初稿改写，Eric Hou 做了独立核验。
唯一的成果是定理 1.1：在每条边失衡度都为正的前提下，MG 是 graphic 的。Imbalance 猜想成立。没有数值 benchmark。
这篇和反例那篇是同一作者、同一工具（GPT-5.6 Sol Max）、同一周发出的姊妹篇。区别在方向：这篇是正面证明，那篇是反例。两篇合在一起，把大模型在开放数学问题上的产出摆得更完整：它既能推翻猜想，也能给出完整证明。对图论本身，这条结果是 imbalance 序列研究的收口，把 2014 年的猜想和 2023 年的计算验证接上了一般情形。