一道20世纪60年代的图论难题终于得解

取一些点，再用线把其中一些点两两相连：数学家把这称为图，把点称为图的顶点，把线称为边。圈是一条经过互不相同的顶点、最后回到起点的闭合回路。一个很自然的问题是：图的边能否被拆分成若干个圈，且每条边恰好用一次？

正如论文所回顾的，答案早已为人所知：当且仅当每个顶点都连接偶数条边时，这才是可能的。这样的图被称为欧拉图。接下来的问题是需要多少个圈。而对于仅靠圈无法完成拆分的图，人们也允许把单独的边作为拆分出的块。

这一猜想

20世纪60年代，**埃尔德什（Erdős）和加莱（Gallai）**猜想：每一个有n个顶点的图，其边都可以被拆分成若干圈和单独的边，总数至多与n成正比——记作O(n)。埃尔德什把它收录进了他的好几部未解问题集。哈约什（Hajós）提出的一个相关猜想则要求，每个欧拉图至多需要(n − 1)/2个圈。

线性是人们所能期望的最好结果：埃尔德什证明了有些图需要大约1.5 n块。问题在于，是否总存在某个常数，使得常数乘以n就足够了。

五十年来缓慢推进的上界

埃尔德什和加莱自己就注意到了一种简单的方法：反复去掉最长的圈。这样大约需要n log n块——据论文所述，这在近五十年里一直是最好的一般性上界。近些年，康伦（Conlon）、福克斯（Fox）和苏达科夫（Sudakov）把它降到了n log log n，随后布契奇（Bucić）和蒙哥马利（Montgomery）又把它降到了n log* n，其中log* n——即需要连续取多少次对数才能使结果小于1——增长得慢到难以想象。这些方法都是分轮进行的，每一轮大约要花费n个圈，因此轮数总会悄悄混进最终的计数中。此外，该猜想已经在一些特殊的图族（例如随机图）上得到了证明。

为回路“买单”的权重

韩国KAIST的**金在勋（Jaehoon Kim）**如今证明了这一猜想：存在一个固定常数C，使得每一个有n个顶点的图都可以拆分成至多Cn个圈和边。作为推论，哈约什猜想在相差一个常数因子的意义下成立。

这一证明放弃了分轮的做法。一个单一的过程每次去掉一个圈或一条边，而总数由两个量控制，每个量都保持在某个常数乘以n以下。

• 基于度数的势函数。 每个顶点被赋予一个权重，它随该顶点的边数增加而减小，大致为1 /（度数 × log²度数）。如果一个圈上各顶点的权重之和至少为1，这个圈就是重的。去掉一个重圈会使整体“势”至少降低1，而这个势的初始值不超过某个常数乘以n。因此，重圈至多只能被去掉O(n)次。
• 顶点的数量。 当不再有重圈时，图就是“轻的”——而主要的新定理表明，一个度数很大的轻图必然包含一个稠密的、几乎封闭的区域。这个区域被拆分成与其规模成正比的若干圈和边，之后其中至少五十分之一的顶点只剩下至多两条边，从而永久退出。由于每个顶点只能退出一次，这一部分的花费也是O(n)。

在图的稠密部分内，路径片段通过穿过“扩张图”的连接路径闭合成一个圈；随机着色让同一个圈的各条连接路径互不相交。——图3，Kim（2026），arXiv:2610.07840。

为了拆分这些稠密区域，证明扩展了布契奇和蒙哥马利关于稳健“扩张图”（expanders）的工具箱——扩张图是指其中每个顶点集合都有许多邻居的图——并对顶点进行随机着色，使同一个圈的各条连接路径永不相撞。

仍未解决的问题

常数C极其巨大，作者也没有尝试去优化它。找到最佳常数（至少为1.5）仍是一个未解问题，精确形式的哈约什猜想，以及加莱提出的一个关于把图拆分成路径的相关猜想，也同样悬而未决。这种加权技巧只要求权重之和收敛，作者认为它或许可以用于其他分解问题。

这是一篇单一作者的预印本，尚未经过同行评审的检验。

利益冲突。 作者声明，在推导论证以及准备文本和图表时大量使用了ChatGPT（OpenAI）和Claude（Anthropic），并已核实所有结果，对论文承担全部责任。您正在阅读的这篇文章也是由Claude撰写的。