诱导四邻接网格森林不一定能通过补点扩充成树¶
任意抽象森林都可以通过增加连接扩充成树，但固定在整数网格上的诱导森林存在额外限制：在保留所有原顶点及全部四邻接边、仅允许添加格点的条件下，有些森林无法成为任何诱导网格树的子图。即使允许任意扩大网格，这种障碍仍然存在。
检索词：诱导网格森林、森林扩充成树、树删除顶点、禁止桥接格点、四连通网格图；induced grid forest, induced tree extension, vertex addition, vertex-deleted grid tree, nonextendable forest, forbidden separator。
模型与准确结论¶
对有限整数格点集 \(F\subset\mathbb Z^2\)，令 \(G(F)\) 包含曼哈顿距离为一的全部顶点对之间的边。问题是：若 \(G(F)\) 为森林，是否总存在有限格点集 \(S\supseteq F\)，使 \(G(S)\) 为树？
答案是否定的。这等价于问：原森林是否一定能由同一嵌入下的一棵诱导网格树删除顶点得到？模型不允许移动、缩放或删除原顶点，也不允许选择性忽略新产生的四邻接边。
| 规模 | 已给出的反例 |
|---|---|
| 小例 | 5×5 网格中，一条 13 点路径和一个孤立点无法补点连接成诱导树 |
| 两个大分量 | 两条各有线性个顶点的路径，之间存在必须经过而又不能填入的格点圈 |
| 多个大分量 | 边长为 \(n\) 的网格中，有 \(\Theta(n)\) 棵树，每棵有 \(\Theta(n)\) 个顶点；任取两棵，即使移除其余分量，也无法补点连成诱导树 |
这里的线性规模相对于网格边长，而非总道路顶点数。嵌套构造的总道路数为 \(\Theta(n^2)\)。
障碍为什么成立¶
若某个空格同时邻接一棵已保留树中的两个不同顶点，填入它就会与树中现有的唯一路径组成环。因此，任何最终包含该树的诱导树都不能包含这个空格。
构造让这类禁止格组成分隔圈，另一个分量被圈在内部。任何连接路径都必须进入分隔圈，因而无法实现；外部有多少空间都不改变这个必经条件。逐层嵌套开缺口的阶梯路径，就得到线性数量的两两障碍。
完整证明给出坐标公式、禁止圈及计数。例如对整数 \(s\ge1\)，取 \(n=12s+1\)，可得到 \(s+1\) 棵树，每棵顶点数介于 \(2n-5\) 与 \(4n-7\) 之间。详见小例、两路径族和嵌套族。
适用范围¶
这否定的是“固定位置的诱导森林总能通过补点变成单树”这一直接归约。允许移动、缩放、改变边模型或分别处理分量的其他归约，需要另外分析。
这个静态构造不是超三次方匹配复杂度的反例。一般森林的候选列表算法仍满足三次方上界。本项结果的状态是“仓库已给出反例族及任意参数下的证明”；有限实例验证是辅助证据，不作外部同行评审声明。
复核与引用¶
在仓库根目录使用 Python 3.10 或更高版本运行：
python topics/simulation/grid-forest-matching/research/verify_tree_extension.py
验证脚本从坐标重新生成全部四邻接边，检查分量大小、森林性质、禁止格及分隔半径。任意参数下的不可扩充性由文字证明保证，不依赖有限枚举。
证明版本：2026-10-12 发布的提交 640ae4a。引用条目 OccamGC2026GridForestTreeExtension 及固定版本链接见引用说明；机器可读的假设与结论见结论索引。