一个AI的证明，为人类重新绘制

画一些点，再用线把其中一些连起来。数学家称之为图；点是顶点，线是边，与一个点相连的线的条数就是它的度。树是一种没有回路、连成一整块的图，就像一根分叉的小树枝；有t个点的树总是有t − 1条线。

20世纪60年代初，保罗·埃尔德什（Paul Erdős）和薇拉·T·绍什（Vera T. Sós）提出了一个简单的问题：多少条线才能迫使一个图包含给定大小的每一棵树？他们的答案，即埃尔德什–绍什猜想，是这样的：

如果一个图的平均度大于t − 2，那么它包含每一棵有t个顶点的树。

这个阈值是精确的。取若干个互不相连的完全图副本，每个有t − 1个点且两两相连：每个点恰好有t − 2个邻居，但没有哪一块大到能容纳一棵有t个点的树。难点在于“平均”二字。如果每个点都至少有t − 1个邻居，就可以毫不费力地一枝一枝地放下一棵树。但平均值对任何单个点都说明不了什么：有些点可能有数百个邻居，有些则几乎没有。

六十年的部分答案

根据论文中回顾的历史，这个问题可追溯到1962—1964年，并成为研究“多少条边会迫使某种模式出现”的数学分支的核心问题。一些特殊情形陆续被攻克：星、路径、双星、分枝很少的树。20世纪90年代初，阿伊陶伊（Ajtai）、科姆洛什（Komlós）、西蒙诺维奇（Simonovits）和塞迈雷迪（Szemerédi）四位数学家宣布证明了非常大的树的情形，但近期论文指出，完整的手稿从未发表。2021年、2024年和2026年又出现了更多部分结果。2026年9月4日，里德（Reed）和斯坦（Stein）发布了针对大型稠密图的证明，并声明这一证明是在没有AI的情况下完成的。

随后出现了一份报告。2026年9月，汤姆·阿达姆切夫斯基（Tom Adamczewski）和托马斯·布卢姆（Thomas Bloom）在一份名为《FrontierMath Erdős》的文件中，把完整猜想的一个证明归功于一个尚未发布的AI模型版本GPT-6 Astra。最初的计数论证已经公开，一个配套的代码库记录了该AI自主寻找证明的过程，以及用证明检验语言Lean完成的形式化验证。报告作者还呼吁人类专家撰写更完整、更传统的阐述。

一次揭示一个点

萨克拉门托加利福尼亚州立大学的杰伊·卡明斯（Jay Cummings）回应了这一呼吁。他27页的文章保留了AI的核心计数论证，但改变了讲述方式：

逐步揭示图。 按某种顺序列出顶点，一次揭示一个，同时揭示已显示顶点之间的边。
要求更多。 不找树的任意副本，而是寻找所选“根”恰好落在第一个顶点上的副本。要求更多反而让证明更容易。
统计早到的邻居。 这些是在这样的副本出现之前就已出现的第一个顶点的邻居。把所有可能顺序下的数目加起来。
给总数设上界。 通过交换顶点或顺序中的整块——这些操作总是可以撤销——卡明斯证明，对所有顺序取平均，早到的邻居至多为t − 2个。

最后一步很短。如果图中不包含这棵树的任何副本，那么在每一种顺序下，第一个顶点的每个邻居都是早到的。对所有顺序取平均，这恰好就是平均度——而按假设，平均度大于t − 2。矛盾：这棵树一定存在。

这个证明只用到度的总和，而不涉及度如何分布。卡明斯还给出了一个概率论版本，并在具体的图上逐步演示了四个和五个顶点的树。

一本图画书式的证明

文章包含32幅图。结尾给出了一个经典推论：用q种颜色给完全图的所有边染色，只要图有q(t − 2) + 2个顶点，就总有一种颜色包含给定的树。在最后的声明中，卡明斯解释说，他是在与ChatGPT的长篇对话中完成这篇文章的；新的呈现思路——早到的邻居、明确的划分、插图——是他自己的；他核查了所有内容，并承担全部责任。

他将自己的阐述与里奥丹（Riordan）和斯科特（Scott）、伍德（Wood）以及弗雷德里克森（Frederickson）的其他近期阐述作了比较，并指出该方法已被推广到有向网络和“超图”，其中一些推广同样归功于GPT-6 Astra。他写道，他的贡献是“以读者为中心的论证可视化阐释，而不是对该猜想的新解决”。