图计数引理

若相关簇对像相互独立的随机二分图，那么选定 $x_1,\dots ,x_k$ 后，每条所需边以概率 $d_{ij}$ 出现，全部边同时出现的比例便是密度乘积。正则性不提供真正独立性，却保证在逐个选顶点时，除了少量异常选择，候选集合在下一个簇中仍保留预期比例。

证明按顶点或退化序逐步嵌入。正则对的一个基本推论是：若 $Y^{\prime }\subseteq V_j$ 仍有 $|Y^{\prime }|\ge \epsilon |V_j|$，则 $V_i$ 中除至多 $2\epsilon |V_i|$ 个顶点外，每个顶点在 $Y^{\prime }$ 中的邻点数都接近 $d_{ij}|Y^{\prime }|$。反复排除异常顶点并相乘候选规模，得到主项；每一步损失累加进 $\eta$。这也说明为什么 $F$ 必须固定：若嵌入步数随 $n$ 增长，误差会持续累积。

取三个簇 $V_1,V_2,V_3$，大小分别为 $3,4,5$，并把每一对簇之间都完全连接。三对密度均为 $1$，任何跨簇选择都形成三角形，所以尊重分部的标号三角形恰有

个，正好等于密度乘积 $1^3$ 乘顶点选择数。若把同一个无标号三角形在固定三部中的位置视为已确定，就不再额外除以 $6$；计数约定必须与公式一致。

现在令三个簇的大小都是偶数 $N$，各自分成相等的“上、下”两半，只在同标签半块之间完全连接。每个簇对的总体密度都是 $1/2$，但跨三部三角形只能全部选上半或全部选下半，共有

个；朴素密度乘积却预测 $(1/2{)}^3{N}^3=N^3/8$。差一倍的原因不是概率计算错，而是每个簇对都被半块见证为不正则。这个反例准确标出正则性假设承担的工作。

密度正下界也不可省略。若 $d_{ij}$ 与 $\epsilon$ 同阶，逐步候选集可能跌到正则定义看不见的尺度。引理保证总副本数，不保证副本边不交，也不保证每个顶点参与近似相同数量的副本；后两种需求要用更强的典型顶点或超图匹配论证。

把正则划分压成约化图后，只要约化图含 $F$ 且对应密度高于固定阈值，计数引理便把这一份 $F$ 提升成原图中的 $\mathrm{\Omega }(n^{v(F)})$ 个副本。这是图移除引理公理库图移除引理Graph removal lemma · H-removal lemma · 图删除引理固定图的副本数若低于正确幂次的足够小比例，就能删除少量边消灭全部该图副本。证明中的矛盾核心，也是以正则性证明 Erdős–Stone 定理时从约化团恢复禁图复制的桥梁。

计数引理还说明稠密图的有限子图统计可由有限密度矩阵近似，是图极限与采样算法的基础。若目标是诱导副本，需要同时乘入非边簇对的因子 $1-d_{ij}$，并要求相关补图簇对也处于可控密度；普通版本不能凭“缺少要求的边”自行完成诱导计数。