三角形移除引理

消灭全部三角形等于选择一组边，击中每个三角形。如果做不到用少量边击中，三角形就必须在全图中广泛分散；正则性把这种“分散”压缩到若干稠密簇对，计数引理随即把一个约化三角形扩增成三次方量级的真实三角形。

重叠方式因此比裸计数更重要。许多三角形若共用同一条边，一次删除即可全部消灭；许多彼此边不交的三角形则各自至少需要一次删除。移除引理断言，在三角形总数低于固定的 $n^3$ 比例时，即使重叠模式最不利，也仍存在一个小的全局击中边集。

“书图”由一条公共边 $uv$ 与顶点 $w_1,\dots ,w_k$ 构成，每个 $w_i$ 同时连接 $u,v$。它有恰好 $k$ 个三角形 $uv{w}_i$，删除公共边 $uv$ 一次便全部消灭。取 $k=6$ 时，八点图含六个三角形但移除数仅为一；逐个三角形各删一边会多付五次，说明局部贪心不是结论本身。

另一端，若图由 $q$ 个边不交三角形组成，则至少要删 $q$ 条边，因为一条边最多击中其中一个三角形。即便取 $q=\lfloor n/3\rfloor$，所需删除数仍只有 $O(n)=o(n^2)$，而三角形数也只有 $O(n)=o(n^3)$，与引理的稠密尺度吻合。

若有 $\epsilon n^2$ 个边不交三角形，任何三角形消除集都至少有 $\epsilon n^2$ 条边；引理的逆否立即推出全图实际上还有 $\delta n^3$ 个三角形，远多于最初列出的边不交族。这就是 Ruzsa–Szemerédi 型结论的核心跃升：二次规模的互不重叠见证会迫使海量额外重叠三角形。

引理只允许删边，不保证删去的边本身稀疏分布，也不保留顶点度。若问题要求删顶点、修改成二分图、排除诱导三角形或处理有向三环，需要不同的 transversal 或诱导移除版本。对只有 $O(n)$ 条边的输入，允许删除 $\epsilon n^2$ 条边过于宽松，不能据此得到有意义的稀疏算法保证。

Ruzsa 与 Szemerédi 用该引理证明：若一个 $n$ 点图的每条边恰属于一个三角形，则其边数为 $o(n^2)$。否则会有正比例于 $n^2$ 的边不交三角形，移除它们需要二次量级边；引理却迫使出现三次量级的全部三角形，与“每条边只在一个三角形中”给出的 $O(n^2)$ 上界矛盾。

把整数三项等差数列编码成三部图中的三角形，并安排来自候选集合的三角形边不交，可由上述结论推出 Roth 定理：正密度整数集合必含非平凡三项等差数列。这里图论引理承担的是从“许多编码三角形”到“出现额外三角形”的放大；额外三角形再解码成所需等差结构。

在性质测试中，若图距离无三角形性质至少 $\epsilon n^2$，随机抽三个顶点命中三角形的概率至少常数阶 $6\delta$。因此只需与 $n$ 无关的随机三元组样本数，就能以固定成功概率拒绝远离性质的图。