← 返回 PaperDaily
大模型与智能体
UCLA最新证明：37年图论悬案再破一类，224万棵树无一例外
1989年Lee猜想提出“所有奇数阶树都是边优美的”，37年来一直悬而未决。这篇来自UCLA的最新论文用零和划分+朗福德序列把“至多一个二度顶点”推进到“至多两个”，还拉上计算机把224万棵树全验证了一遍。硬核、漂亮、可复现，图论爱好者不容错过。
龙哥读论文
发布于 2026-09-05 00:31:07
阅读 3
查看原文
原论文信息如下：
先讲一个有点“无聊”的小游戏：给一棵树的每一条边编上1到q的号码（q是边的总数），然后算每个顶点的“边号和”，如果这些边号和模p（p是顶点总数）之后恰好得到0到p−1每个数字各一次，那么这棵树就被称为“边优美的”（edge-graceful）。听起来就像个数字填字游戏，对不对？但就是这个看似人畜无害的小游戏，已经折磨了图论学家将近40年。
1985年，Lo正式定义了边优美标号，并指出一个必要条件：q(q+1) ≡ p(p−1)/2 (mod p)。这个条件放在树上非常苛刻——它直接排除了所有偶数阶的树，也就是说，一棵树要想边优美，顶点数必须是奇数
Lee猜想（1989）
37年过去，这个猜想依然悬而未决。期间Gallian的动态综述里记录了零星几个蜘蛛图（spider）家族的成果，以及一条来自“反魔幻标号”（antimagic labeling）文献的强结果——Kaplan、Lev和Roditty证明了：如果在树根处让每个非叶节点至少有俩孩子图论难题的又一次突破：边优美树猜想的新进展 先从游戏说起。给一棵树的每一条边发一个不重复的号码牌，号码从1编到q（q是边的总数）。接着算每个顶点的"得分"：把它所有相邻边的号码加起来，再对顶点总数p取模。如果每个顶点最终得到的模值恰好是0到p−1各出现一次，这棵树就是边优美的
这游戏是1985年Lo在一篇会议论文里正式"立项"的。Lo顺手证了一个必要条件：q(q+1) ≡ p(p−1)/2 (mod p)。这个条件放到树上非常残酷——它直接把所有偶数阶的树一票否决。换句话说，一棵树要想边优美，顶点数必须是奇数
于是1989年Lee提出了那个著名的猜想：所有奇数阶的树都是边优美的
所谓二度顶点
更硬核的是，作者不只是写了定理和证明，还把n≤25范围内所有恰好有两个二度顶点的奇数阶树——一共2,245,070棵
从零和划分到Langford序列：核心证明思路解析 证明的第一步，是做一个"根化转换"（rooted reformulation）。把树选定一个根r，令根的值g(r)=0，其他每个顶点v的值g(v)定义为它到父节点那条边的标号。这样一来，g就变成了从顶点集V到Z_n（模n的整数集合）的一个双射——因为每条边恰好对应一个非根顶点。
然后看每个顶点v的"和"h(v)：它等于自己的值g(v)加上所有孩子节点的值之和，再取模n，即
h(v) ≡ g(v) + Σu: p(u)=v g(u) (mod n) 如果每个内部顶点v的"孩子块"B_v={g(u): p(u)=v}之和都恰好为0模n，那h(v)就直接等于g(v)，问题瞬间收工——g本来就是双射，h自然也是。然而二度顶点在这里露出了獠牙：它只有一个孩子，所以它的孩子块是一个单元素集合，一个非零元素怎么凑也凑不出0。除非这个元素本身就是0，但0是根的专属值，不能给别人用。
前人的零和划分方法正是撞死在这块石头上。而这篇论文换了一个思路：不要求每个孩子块严格为零和，而是允许个别顶点出现已知偏差，最终让h成为g复合一个小置换的结果
有了这个战略，接下来是战术层面的工具。第一个工具叫对称对
第二个工具更关键，叫孪生三元组
这个观察看起来只是简单算术，但它巧妙地把"三个对称对"重新包装成了"两个零和三元组"。这样一来，凡是奇数大小的孩子块，都可以通过接收一个零和三元组来凑平。论文还证明了它的逆命题：Z_n \ {0}里的每一个零和三元组，必然来自某个可接受指标三元组。也就是说，孪生三元组是唯一的生成途径，没有漏网之鱼。
接下来要解决的是一大坨指标怎么高效地打包成三元组。工具是朗福德序列
这一整套组合拳的逻辑可以概括为：先找一个特殊根、设计几个固定的gadget块吸收二度顶点的偏差，剩下的指标区间全部利用朗福德序列打包成孪生三元组，每个三元组再拆成两个零和三元组分给两个奇数大小的块。对称对直接当"双数配平"用。这样一来，整棵树的所有内部顶点都能分配到和符合要求的块，从而构造出边优美标号。
小工具目录：巧妙处理二度顶点的关键设计 两个二度顶点a和b在树里的相对位置五花八门：可能离得远、可能共享同一个邻居、甚至可能直接手拉手相邻。不同的位置关系对构造的要求完全不同。本文的应对方式是：先把问题归约到几种标准形态，然后为每种形态准备一个"小工具"（gadget）。
先看根怎么选。论文的根选择引理（Lemma 6）给出了漂亮的三分法：如果a和b相邻，至少有一侧的外邻居是分支顶点，把根放在那里，让a–b链直接挂在根下方；如果a和b不相邻但有个共同邻居w，那w必然是分支顶点（因为树里不会有别的路），直接把根放在w，a和b就都是根的孩子；否则随便选一个分支顶点当根，此时a和b各有不同的父节点。
这个"根选择+归类"的智慧在于：把千变万化的二度顶点位置压缩成有限的几个标准情形，然后一张表就能搞定。论文的Table 1列出了各种情况下的预设方案——这是整个构造的"核心配件库"。
图中展示了各种情况的配件选择：比如最省心的偶/偶情形，两个二度顶点的孩子块各放入一对相反数{1,−1}和{3,−3}，各自和为0，删掉兜底的{±2}即可。奇/奇情形要复杂一些：每个二度顶点的块放一个零和三元组{1,3,−4}之类的组合，同时需要一个"宿主"顶点接收镜像三元组。相邻情形则用一条链上的3-循环来吸收偏差。混合情形把"对"和"三元组"搭配使用。
表1：小工具目录。展示了不同情况下的参数选择；镜像混合情况交换a和b的角色。
表里的每一行都经过仔细验证：所有预设的元素必须互不相同且非零，合并被删掉的索引后仍是一个完整的对称对集合，同时块的大小和数量要匹配。装配命题（Proposition 7）保证了：只要按照表中的方案分配这些预设值，最终h就是g复合一个不超过3个位置的小置换（对换或3-循环），所以h依然是双射——标号自然就边优美了。
还有一处细节值得点赞：树里不能有第三个二度顶点，所以任何奇数大小的块至少能容纳3个元素，正好放得下一个零和三元组。块和三元组之间的配对关系也严格成立：奇数块的个数是偶数（从总块数减去3为偶数可以推出），所以三元组总是成对消耗，和打包引理的孪生结构恰好对上。整套装配流程严丝合缝。
计算机辅助验证：2,245,070棵树的完整检验 图论证明最怕的是什么？是"看起来对但漏了一个边角情况"。这篇论文在严谨性上做得相当扎实，验证分为三个层面。
第一层：全量枚举。对n≤25的所有奇数阶且恰好有两个二度顶点的树，程序逐棵构造标号并验证。数量分布为n=7,9,...,25时分别是2、10、46、204、908、4070、18390、83628、382326、1755486棵，合计2,245,070棵
第二层：独立复检。论文提供了一套与构造函数完全独立的检查器，代码零共享，对全部224万多个证书重新核验，报告零违规。也就是说，即使构造程序本身有bug，检查器也能把它揪出来。
第三层：对打包引理本身的检查。n≤301的范围，所有用到的指标集都通过有界回溯搜索找到了最大打包，并以witness形式存档，可以逐三元组精确验证。少数确实无法打包的极端情况（如n=21时[5,K]无法打包）穷举枚举证明了不可行——而这些情况构造根本用不到。n>301的部分，打包引理的每个分支（窗口算术和Simpson条件）都对所有奇数n≤5001做了符号化检查，n更大时的逻辑就是统一的构造，不再依赖计算机。
这套"全量枚举+独立检查+符号验证"的组合，把"无限"压缩成了"有限+统一"，既不是草率的大型计算，也不是无凭据的"计算机证毕"。作者还把全部代码和数据集放在了Zenodo上，附了一个一条命令就能重跑所有验证的脚本。对于想要检验结果的研究者来说，这是最友好的姿态。
讲真，对着224万多棵树一棵一棵地发"号码牌"，这工程量光是想想就让人头皮发麻。但它真的做到了。
总结与展望：通向完整猜想的下一步 这篇论文把Lee猜想的已知边界从"至多一个二度顶点"推进到了"至多两个"，方法和结论都干净利落。但距离完全猜想（所有奇数阶树）还有多远？
作者在论文末尾很诚实地指出了方法的天花板：这套构造并不本质限制在"两个"二度顶点——每多一个二度顶点，就多一个"单元素块"需要吸收，gadget可以做，但簿记复杂度会迅速失控。作者没有去追k≥3的情形，这个判断相当理性。
另一个值得关注的线索是偶数阶的树。偶数阶树不可能边优美（Lo的必要条件已排除），但论文考虑了一个变体：把模数从n改成n+1，让顶点和模n+1互异。对n≤18的穷举计算发现，除了星形树（所有偶数阶都不行）和唯一的6顶点双星之外，其余偶数阶树居然都满足这个弱化条件。这个观察虽然只是探索性的，但或许能启发新的研究方向。
想完整证明Lee猜想，核心瓶颈始终是：如何用一套统一且可管理的构造，处理任意多个二度顶点的组合。目前的方法像是一个手工打造的"工具箱"——每个新情形都要手工调整参数。未来如果能把这套gadget系统化、模块化，甚至用递归的方式生成"多链处理方案"，或许就能触碰完整的猜想。论文中那句"bookkeeping grows quickly"既是坦诚，也是留给后来者的挑战书。
龙迷三问 这篇论文到底在解决什么问题？ UCLA学者结合零和划分与兰福德序列，证明奇数阶且至多两个二度顶点的树均边优美，将1989年李氏猜想推进一大步；224万棵树计算验证全通过，并扩大反魔幻树家族。这篇工作最值得看的点是什么？ 论文通过计算验证了所有奇数阶n≤25且恰好有两个二度顶点的2,245,070棵树均存在边优美标号，并给出了可验证的证书。这篇工作的边界或风险在哪里？ 优点：理论证明严谨，构造方法系统，计算验证充分；缺点：仅覆盖至多两个二度顶点的情况，对k≥3个二度顶点的情况未涉及，且部分证明依赖计算机辅助验证。如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★☆
通过将边优美标号问题转化为根树上的零和块划分问题，结合Langford序列和孪生三元组构造，证明具有至多两个二度顶点的奇数阶树均为边优美图。实验合理度： ★★★☆☆
现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。学术研究价值： ★★★★☆
通过将边优美标号问题转化为根树上的零和块划分问题，结合Langford序列和孪生三元组构造，证明具有至多两个二度顶点的奇数阶树均为边优美图；更关键的是问题定义是否可复用到同类任务。稳定性： ★★★☆☆
现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。适应性以及泛化能力： ★★★☆☆
现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。硬件需求及成本： ★★★☆☆
现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。复现难度： ★★★☆☆
现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。产品化成熟度： ★★★☆☆
论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。可能的问题： 仅覆盖至多两个二度顶点的情况，对k≥3个二度顶点的情况未涉及，且部分证明依赖计算机辅助验证。
[1] Lo S. On edge-graceful labelings of graphs. Congressus Numerantium, 1985, 50: 231-241. [2] Lee S M. A conjecture on edge-graceful trees. Scientia, 1989, 3: 45-47. [3] Kaplan G, Lev A, Roditty Y. On zero-sum partitions and anti-magic trees. Discrete Mathematics, 2009, 309(8): 2010-2014. [4] Simpson J E. Langford sequences: perfect and hooked. Discrete Mathematics, 1983, 44(1): 97-104. [5] Meng L. Trees of odd order with at most two vertices of degree two are edge-graceful. arXiv:2608.23881, 2026. [6] Supplementary materials (certificates, checker, witnesses). Zenodo, doi:10.5281/zenodo.22085671. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
一棵树，两颗“二度果”，零和划分加朗福德序列，37年悬案又啃下一块硬骨头🍖 图论之美，在于一行构造也能见证百年猜想～欢迎加入龙哥读论文粉丝群，
扫描下方二维码或者添加龙哥助手微信号加群 ：kangjinlonghelper。
一定要备注：研究方向+地点+学校/公司+昵称（如 图论+上海+UCLA+龙哥） ，根据格式备注，可更快被通过且邀请进群。
*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
