图移除引理

若 $H$ 副本很少，人们希望从每个副本删一条边；问题在于副本可能大量重叠，逐个处理会反复计费。移除引理的结论反而说：在稠密尺度下，若没有一小组边能够击中全部副本，那么副本就不可能只是“略多”，而必须达到 $n^h$ 的正比例。

正则性证明路线 ​

先对 $G$ 作 Szemerédi 正则划分。删除异常集关联边、各簇内部的边、所有不正则簇对的边，以及密度低于阈值的正则簇对边；先把簇数下界取得足够大，再依次选好其余参数，总删除量便不超过 $\epsilon n^2$。若剩余图仍含一份 $H$，把其顶点映到所在簇会得到 $H$ 到约化图的同态；必要时将同一簇细分成若干大子块，便可让不同顶点占据不同位置。图计数引理公理库图计数引理Graph counting lemma · Counting lemma for regular pairs · 正则对计数引理固定小图的各条边若落在足够正则且密度有下界的簇对上，其跨簇副本数接近独立密度乘积。随即在原图中产生 $c{n}^h$ 个 $H$ 副本，与“至多 $\delta n^h$”矛盾。于是剩余图必为 $H$-free。

这个证明也展示量词为何呈嵌套：先由目标删除误差选密度阈值和正则误差，再由计数引理得到副本常数 $\delta$。直接把 $\delta$ 先固定为任意常数，无法保证删除预算。

由 $n/3$ 个互不相交三角形组成的图只有 $n/3$ 个三角形，删除每个三角形的一条边即可，共删 $n/3=o(n^2)$ 条。这与引理一致：副本数远低于 $n^3$，图也只在稠密编辑尺度上极近于无三角形性质。它提醒我们，引理没有承诺用 $O(\mathrm{\#}H)$ 以外更神奇的方式删除；结论的力量在于删除数相对 $n^2$ 很小。

反向看，完全三部图 $K_{m,m,m}$ 有 $n=3m$ 个顶点和恰好 $m^3=n^3/27$ 个跨部三角形。每条边只属于 $m$ 个三角形，所以任何击中全部三角形的边集至少有 $m^2$ 条；删去任意一对部之间的全部 $m^2=n^2/9$ 条边又确实可行。这给“二次编辑距离对应三次副本数”一条可核算轨迹。

引理要求 $H$ 固定。若 $h=h(n)$ 增长，正则与计数参数不会保持统一。它也属于稠密模型：一个只有 $O(n)$ 条边的图总能删 $o(n^2)$ 条边清空，所以结论对稀疏性质测试可能近乎空洞；稀疏移除引理必须以宿主伪随机性或实际边数重新定标。

普通移除只允许删边，因为删边保持“没有普通子图”的单调性。诱导 $H$-free 性质既可能需要删边也可能需要加边，对应的诱导移除引理更强，不能由这里的单调版本一句话推出。

取 $H=K_3$ 得到三角形移除引理公理库三角形移除引理Triangle removal lemma · 三角形删除引理三角形副本数为顶点数三次方的小比例时，删除顶点数平方的小比例条边即可消灭全部三角形。，它是 Roth 三项等差数列定理的经典图论证明核心。一般图移除引理还推出稠密图中每个有限禁子图刻画的单调性质都可作常数查询的单边错误测试：随机抽取常数个顶点，若图远离性质，就以常数概率看见禁图。

移除引理与超饱和公理库极值图中的超饱和Supersaturation in extremal graphs · Erdős–Simonovits supersaturation theorem · 超饱和定理图的边密度固定超过禁图极值密度时，禁图副本数必从一个跃升到顶点数的正确幂次量级。方向相近但假设不同。超饱和以边密度超过极值阈值为输入；移除引理以编辑距离远离 $H$-free 为输入。一个图可以边密度不高却分散着许多局部副本，故两者不能互相用一句密度比较完全替代。