M23
树的素标号：n ≤ 26 全体机器验证与新树族的完整证明
来源说明：本则出自独立撰写的第二批方案。它与前 20 则同样遵循八块结构与硬门槛要求，但撰写时未做英文文献检索，新颖性边界依据的是历届获奖图谱与既有知识，而非当轮查新。因此其「需核实」条目更多，启动前须自行补一轮英文检索。
1 · 研究问题
所有 n ≤ 26 个顶点的树是否都有素标号（prime labeling，即顶点可用 1…n 标号使每条边两端标号互素）——Entringer–Tout 猜想在该范围内是否无反例？能否对一个此前未被覆盖的树族（如直径 ≤ 5 的树或腿长受限的蜘蛛树扩展族）给出素标号存在性的完整构造性证明？
2 · 研究背景与空白
素标号是图标号理论的经典对象：把 1…n 分配给树的 n 个顶点，要求相邻顶点标号互素。Entringer–Tout 猜想断言每棵树都有素标号。它把图结构与整数互素结构耦合，验证是纯离散判定，非常适合穷举 + 构造证明的组合拳。
已有工作：该猜想对"充分大的树"已被证明（需核实：搜索关键词 Haxell Pikhurko Taraz primality of trees sufficiently large），但"充分大"没有给出可用的显式界，小与中等规模仍靠逐族证明与机器验证；路、星、毛毛虫、蜘蛛、完全二叉树等多个树族已有构造证明（Gallian 动态综述《A Dynamic Survey of Graph Labeling》收录，免费公开）；机器验证的已知范围需核实（搜索关键词 prime labeling trees verified computationally up to）。丘奖相邻获奖论文：2020 优胜奖《On the coprime labelings of hypergraph》把互素标号推广到超图。
空白在：显式验证范围与"已证明树族清单"之间存在大量缝隙（如小直径树、受限叶数树），且验证范围本身可被普通笔记本实质推进。适合学生：判定完全离散、剪枝策略本身有数学内容（大素数顶点必须放在叶或特定位置）、失败模式温和。
3 · 可检验假设
- H1：全部 n ≤ 26 的非同构树（n = 26 时约 2.8×10⁸ 棵，OEIS A000055）均有素标号。
- H2：所选新树族存在统一的构造性素标号方案，可用归纳法完整证明（若构造失败，则该族中的最小反例结构可刻画）。
4 · 量化验收标准
- 方法学校验（硬门槛）：标号搜索器先复现已知结果——(a) 对路 Pₙ、星 K₁,ₙ、毛毛虫的已发表构造逐一机器验证（n ≤ 10³ 抽样 100 例零违例）；(b) 与独立暴力搜索在全部 n ≤ 12 的树（共 551 + … 棵，A000055）上结果完全一致。不过关则全线无效。
- 验证交付：n ≤ 24 全体树验证完成（约 3.9×10⁷ 棵）为及格线，n ≤ 26 为目标线；给出每棵树找到标号的平均回溯步数分布。
- 证明交付：一个此前未覆盖树族的完整构造证明（覆盖情况第 4 周文献核实后锁定目标族）。
- 剪枝有效性量化：报告关键剪枝（素数位置约束、度约束）各自带来的加速比。
- 代码开源、树生成用标准工具、一键复跑。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 非同构树生成 | nauty 的 gentreeg（pallini.di.uniroma1.it），流式输出避免存盘 |
| 树计数对照 | OEIS A000055（仅校验生成器，不计入贡献） |
| 已证明树族清单 | Gallian《A Dynamic Survey of Graph Labeling》（Electronic Journal of Combinatorics 网站免费下载） |
| 标号搜索 | 自写回溯 + 位掩码互素表；PyPy 或 C 提速 |
| 算力量级 | n = 24 全体约 3.9×10⁷ 棵，单棵平均毫秒级 → 笔记本约数天；n = 26（2.8×10⁸ 棵）约 1–3 周后台运行，可分段断点续跑 |
6 · 方法路径
- 搭建 gentreeg 流水线 + 回溯搜索器，完成第 4 块第 1 条校验。
- 文献窗口：从 Gallian 综述整理"已证明树族清单"与已知机器验证范围（能力边界核实步），锁定目标新族。
- 逐层推进验证 n = 13 … 26，断点续跑，记录难例（回溯步数最高的树）。
- 分析难例的结构共性（大素数位置受限的树形），提炼目标族的构造方案。
- 完成目标族构造证明（归纳 + 显式标号公式），机器验证构造在 n ≤ 10³ 内零违例。
- 独立交叉校验：用另一种搜索顺序（按素数从大到小放置）复算全部 n ≤ 20 结果一致。
7 · 新颖性边界
- 本课题不声称证明 Entringer–Tout 猜想，不把"充分大树已证"的已有定理计为本项目结果，也不把 Gallian 综述里已覆盖的树族重复声称。
- 已有工作：充分大树情形已证（文献第 4 周核实）；路/星/毛毛虫/蜘蛛等族已有构造；既有机器验证范围需核实。丘奖相邻获奖论文：2020《On the coprime labelings of hypergraph》——本题差异：对象是树的经典素标号而非超图推广，交付是显式验证范围推进 + 新族证明。
- 本项目贡献（主结论）：验证范围的显式推进（n ≤ 24/26）+ 一个新树族的完整构造证明 + 难例结构分析。
- 价值：给中心猜想补上"显式小规模无反例 + 新族"两块拼图，且验证结果可被任何人复跑核对。
8 · 决策门槛（go / no-go）
- 第 4 周末：完成文献核实。若发现机器验证已覆盖 n ≥ 26（则验证贡献缩水）→ 把验证目标改为"带约束版本"（如强素标号/互素标号变体，Gallian 综述含清单），搜索器复用，框架不变。
- 第 8 周末：n ≤ 18 验证完成且单树平均耗时 ≤ 10 ms。若性能不达标 → 改用 C 重写核心回溯；仍不达标则验证线止步 n = 22，主结论改以"新族证明 + 难例分析"为主。
- 第 24 周末：目标族证明若卡住，降级路径：改证该族的子族（如腿长 ≤ 3 的蜘蛛扩展），或改证"该族中反例必含的结构"——两条都保留"验证 + 族证明"的主结论框架。
- 预算裁剪顺序：n = 26 层 → n = 24 层 → 难例分析章节；砍完主结论仍成立。