依赖随机选择

随机选一个顶点时，高度顶点更容易落入它的邻域；同时选 $t$ 个顶点再取公共邻域，会把这种偏好放大到 $t$ 次方。因此高连接度的顶点在公共邻域中获得更大的权重。所得集合起初仍可能含少数“坏”的 $r$ 元组，方法再为每个坏组删掉一个顶点，用很小的规模损失换取对所有剩余 $r$ 元组的统一保证。

名称中的“依赖”指最终选出的顶点通过共享随机样本而相关，并非先假设原图边独立。输入图可以完全确定；随机性只存在于证明过程。它是概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。：通过期望界证明至少一次抽样达到所需规模与结构。

引理证明 ​

从 $V(G)$ 独立均匀、有放回地取 $t$ 个顶点组成多重集 $T$，令 $A=N(T)$。对每个顶点 $v$，事件 $v\in A$ 的概率为 $(d(v)/n{)}^t$。对凸函数 $x\mapsto x^t$ 在 $[0,\mathrm{\infty })$ 上应用有限等权Jensen 不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。，得到

令 $Z$ 为 $A$ 中共同邻点少于 $m$ 的坏 $r$ 元组数。每个坏组 $S$ 被包含于 $A$ 的概率小于 $(m/n{)}^t$，故

由一阶矩理路一阶矩方法First moment method用坏事件计数的期望小于一或 Markov 型界证明好对象存在。，某次抽样满足 $|A|-Z\ge a$。从每个坏组删除一个顶点，剩余集合大小至少 $|A|-Z$，且不再含坏 $r$ 元组。条件式中的两项分别控制初始集合规模与删除损失。

设二分图左侧为 $A=\{a_1,\dots ,a_5\}$，右侧为 $B=\{b_1,\dots ,b_4\}$，并令

从 $B$ 有放回取两个点。共同邻域期望为

若恰抽到 $b_1,b_2$，得到 $N(b_1)\cap N(b_2)=\{a_1,a_2,a_3\}$；其中任意两点在原图中至少有两个共同的 $B$ 侧邻点。这个轨迹展示抽样对象是共同邻域，而不是随机保留边。

引理控制的是 $U$ 中各个 $r$ 元组在原图里的共同邻域。二分图例子中的 $U$ 位于同一侧，内部甚至没有边，却具有所需的共邻性质。对更大的顶点组、嵌入计数或算法效率，可以进一步设计迭代、嵌套或确定化版本。

有了“每个小子集都有许多共邻点”，可以按一侧顶点的顺序贪心嵌入二分图：每放入一个新顶点，都从尚未耗尽的共同邻域选像。由此可证明一侧最大度至多 $r$ 的固定二分图拥有 $O(n^{2-1/r})$ 型极值上界，并处理细分图、偶圈和 Ramsey 型嵌入。

KST 定理理路Kővári–Sós–Turán 定理Kővári–Sós–Turán theorem · KST theorem · 科瓦里–索什–图兰定理通过共同邻域的凸性计数，为不含固定完全二分子图的图给出次二次边数上界。也围绕共同邻域计数，但直接把总量上界与度数凸性下界比较。上述 DRC 引理则独立地抽样、控制坏组并删点，得到一个子集中“每个小组都有许多共邻”的一致性；其证明没有调用 KST 的极值结论。二者可以用于相近的密度尺度，DRC 的一致性还便于嵌入更复杂的二分图，却不替代具体 Zarankiewicz 问题中的精确计数。