M03
树的奇素数标号猜想：n ≤ 20 全树穷举验证与蜘蛛树类的构造性证明
1 · 研究问题
所有 n ≤ 20 的树是否都有奇素数标号（odd prime labeling：顶点标 1,3,…,2n−1，相邻标号互素）？在已证类（梯图、完全二叉树、部分毛虫树）之外，能否对蜘蛛树（spider）等已知素树类给出构造性证明？
2 · 研究背景与空白
素标号（prime labeling）由 Entringer–Tout 猜想驱动："每棵树都是素图"。已证：n ≤ 15（Fu–Huang 1994）、n ≤ 50（Pikhurko 2007）、充分大的树（Haxell–Pikhurko–Taraz 2011）。奇素数标号是 2020 年前后提出的变体（On odd prime labeling of graphs, 2020；arXiv:2208.08488, 2022），核心猜想为"每个素图都是奇素图"，已证类包括梯图、完全二叉树、堆叠棱柱、若干毛虫类，以及除个别参数外的 Km,n。
空白在该猜想在树类上没有任何系统穷举验证记录，且蜘蛛树、橄榄树、香蕉树等经典素树类的奇素性未定。适合学生：验证器技术门槛低、每棵树自带证书、找到反例即推翻猜想（重大正结果），找不到则给出验证边界与从数据中提炼的构造（负结果同样成文）。
历届对照：2020 年优胜奖《On the coprime labelings of hypergraph》做的是超图互素标号，对象与标号集都不同，见第 7 块。
3 · 可检验假设
- H1：n ≤ 20 的全部约 1.35×10^6 棵非同构树均有奇素数标号（猜想在树上无小反例）。
- H2：蜘蛛树全类（或至少"腿长 ≤ 2 的蜘蛛"与橄榄树）可构造性证明奇素，构造从穷举数据的标号模式中提炼。
4 · 量化验收标准
- 方法学校验（硬门槛）：自建回溯标号器复现两组已知结果——(a) n ≤ 12 全树皆有素标号（与 Fu–Huang 结论一致）；(b) 文献中梯图 Ln（n≤10）与完全二叉树（≤4 层）的奇素标号存在。任一不吻合则后续无效。
- n ≤ 20 全树穷举，每棵输出标号证书或标记为反例；候选反例必须由第二套独立实现（不同作者/不同算法顺序)复核确认。
- 报告回溯难度分布（节点数 vs 最大度/直径），作为结构分析数据。
- 至少一个新树类的构造性证明，构造须给出显式标号函数并归纳验证。
- 全部代码、证书与树生成流程开源。
5 · 数据与工具
| 用途 | 来源 / 工具 |
|---|---|
| 非同构树生成 | nauty 的 gentreeg（免费，需自行编译，第 2 周核实安装）；备选 networkx nonisomorphic_trees（内置但慢，n ≤ 16 可用） |
| 标号搜索 | Python 自写回溯（无现成库）：奇标号与偶度顶点约束剪枝 + 大素数标签优先放高度顶点；预计平均 <10 ms/棵，n ≤ 20 全量单核数小时 |
| 互素判定 | math.gcd（内置）；标号图谱对照 Gallian 动态综述——仅校验用，不计入贡献 |
| 反例复核 | 第二实现用约束求解（pysat 或 pulp）交叉确认 |
6 · 方法路径
- 实现回溯器并完成第 4 块第 1 条双重校验。
- 核实 gentreeg 安装与 n=18–20 的树流生成速度（工具能力核实点）。
- 逐层跑 n ≤ 16 → n ≤ 18 → n ≤ 20，存全部证书。
- 统计难例结构，提炼蜘蛛/橄榄树的标号模式。
- 把模式写成显式标号函数，用互素性逐边验证并做归纳证明。
- 独立交叉校验：抽样 10^4 棵树用第二实现复算存在性结论。
7 · 新颖性边界
猜想"每个素图都是奇素图"非本项目提出（2020/2022 文献，点名见第 2 块），已证类也已发表。历届丘奖 2020 年《coprime labelings of hypergraph》研究超图上的互素标号，与本题的树 + 奇标号集互不覆盖。本项目贡献（主结论）：该猜想在树类上的首个大规模穷举验证记录（含证书与难度谱）+ 至少一个新类的构造证明。价值：反例即推翻公开猜想；无反例则把验证边界从零推到 n=20 并新增已证类。"未发现反例"是有效结论，因为每棵树附可机检证书。
8 · 决策门槛（go / no-go）
- 第 3 周末：校验全过 + gentreeg 可用。若 gentreeg 编译失败 → 用 networkx 顶到 n ≤ 16，并把上限调整写入论文（框架不变）。
- 第 8 周末：实测 n = 18 全层耗时。若 > 1 周单核 → 降级一：全量上限 n ≤ 17 + n = 18–20 随机抽样 10^5 棵；主结论改述为"全量至 17、抽样至 20"。
- 第 16 周末：若构造证明卡住 → 降级二：主结论为穷举记录 + 难例结构定量分析（回溯代价与树参数的回归，给自助法置信区间）；证明部分降为猜想。
- 已知风险：n=20 层数据量（约 8×10^5 棵）证书存储 ~GB 级，需流式写盘；第 10 周前核实。