图移除引理

副本数的尺度是 $n^h$，删除边数的尺度是 $n^2$。例如三角形只有 $\delta n^3$ 个时，逐个删除一条边仍可能给出远大于 $n^2$ 的计费上界。移除引理利用副本之间的整体结构，把“副本比例很小”转成“一小组边就能击中全部副本”。

正则性证明路线 ​

先对 $G$ 作Szemerédi 正则划分理路Szemerédi 正则性引理Szemerédi regularity lemma · Graph regularity lemma · 塞梅雷迪正则性引理任意充分大的稠密图都能分成有界多个等大顶点簇，使绝大多数簇对在大子集尺度上呈现近似均匀密度。。删除异常集关联边、各簇内部的边、所有不正则簇对的边，以及密度低于阈值的正则簇对边；先把簇数下界取得足够大，再依次选好其余参数，总删除量便不超过 $\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)$ 条。图中虽有线性数量的三角形，归一化删除距离却趋于零，符合引理采用的稠密尺度。

反向看，完全三部图 $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 为输入。一个图可以边密度不高却分散着许多局部副本，故两者不能互相用一句密度比较完全替代。