GPT-5.6 找到 18 顶点反例，证伪悬置 31 年的 Teschner 猜想

2026-08-11

GPT-5.6 生成的 18 顶点三次二部图，约束数 b(G)=5 大于 (3/2)Δ(G)=4.5，证伪 Teschner 1995 猜想；论文自带 Python 验证器复跑通过。

这篇在解决什么

图论里有个量叫 domination number（控制数）γ(G)：最少选多少个顶点，能让每个顶点要么自己在选集里、要么挨着一个选中的顶点。bondage number b(G) 是它的脆弱度版本，指最少删掉多少条边能让控制数变大。1995 年 Teschner 证明了控制数不超过 3 的图都满足 b(G) ≤ (3/2)Δ(G)，其中 Δ(G) 是最大度，并猜想这个上界对所有图都成立。之后三十多年，人们在许多图类上证出了它，Gagarin 和 Zverovich 2013 年还专门处理过拓扑曲面上的图，但一般情形一直没人堵上。这篇出手的方向相反：它给了一个反例，把猜想证伪。

方法

反例是一个 18 个顶点的三次（每个顶点度数都是 3）、二部（顶点能分成互不相邻的两拨）、连通的图。论证分三步，全部可手工核对或可复算：

• γ(G)=6。先排除任何 5 元控制集存在。办法是按二部划分做计数：若选 a 个 X 顶点、5−a 个 Y 顶点，则没选中的 X 顶点只能靠那 5−a 个度数为 3 的 Y 顶点覆盖，没选中的 Y 顶点只能靠那 a 个 X 顶点覆盖，两边的不等式夹出 a 只能取 2 或 3。再把两顶点邻域必须不相交、并集恰好覆盖六个点的条件穷举，每种情况都剩一个顶点没人管。最后给一个具体的 6 元控制集 D₀={0,1,2,3,14,15}，于是 γ=6。
• b(G)≤5。删掉与相邻顶点 0、6 关联的五条边 F₅，0 和 6 变成孤立点，剩下 16 个顶点的子图控制数是 5，加上两个孤立点 γ 跳到 7，大于原来的 6。
• b(G)≥5。这是全篇唯一靠机器的部分。穷举全部 C(18,6)=18564 个 6 元集，确认恰好 297 个是控制集；再对全部 C(27,4)=17550 个 4 边删除方案逐个测试，每种都至少留下一个 6 元控制集仍然有效。删 4 条边压不住，必须删 5 条。

承重的是 Lemma 2.2（束判据）：一个控制集 D 删边后是否还控制，等价于每个 D 外顶点连向 D 的那束边没被整个删掉。穷举就建立在这条上。

论文附录那段 Python 原样复跑，另加测两项（任何 5 元集都不控制、F₅ 之后 7 能控制而 6 不能），全部通过。这个反例的计算部分可独立复算，确实成立。

结果

唯一的成果就是这个反例：b(G)=5，大于 (3/2)Δ(G)=4.5，Teschner 猜想被证伪。没有 benchmark 表，因为这不是跑分的活。

为什么重要

两个层面。数学上，一个悬置 31 年的猜想以最小可能的方式倒掉：反例出在三次图（度数最低的非平凡情形），说明 3/2 这个系数连最温和的图类都守不住。AI 上，这才是中文圈真正在聊的点。作者在生成式 AI 声明里写明，这个反例是 OpenAI 的 GPT-5.6 Sol 在 max reasoning 档、由作者出题后生成的，作者随后改写、补细节、独立核验并署名负责。这把大模型在数学上的角色从「做竞赛题」（AlphaProof 解 IMO）又往前推了一步：直接对一个开放猜想构造反例。

局限与存疑

• 这是 figshare 上的预印本，没过同行评议。
• 能被复算验证的只有计算部分（γ=6、b≥5、b≤5）。γ=6 那段排除 5 元集的手工论证没有逐行重推，只是采信作者；好在那段和「5 元控制集数为 0」的穷举结果一致，可信度较高。
• 关于「GPT-5.6 Sol Max」具体是什么模型、用什么提示、模型独立产出到什么程度、作者改了多少，论文只给了一段声明，没有细节。功劳算给模型还是算给做核验和编辑的人，目前无从分辨。
• 作者 Yousof Yavari 是加拿大 UBC 的学生，Eric Hou 做了独立核验，但核验到什么深度论文没说。

术语

• domination number γ(G)（控制数）：最少选多少个顶点，使每个顶点要么在选集中、要么与选集中的点相邻。
• bondage number b(G)（约束数）：最少删多少条边能让控制数变大，衡量图的控制结构有多脆。
• Δ(G)（最大度）：图中顶点的最大邻居数。
• cubic / 三次图：每个顶点度数都是 3 的图。
• bipartite / 二部图：顶点能分成两拨、所有边都跨两拨的图。

原文与代码

• 原文

社区讨论

• GPT-5.6 解决两道困扰数学界十余年的图论难题 No-Performer-2242

全部论文解读