依赖随机选择

随机选一个顶点时，高度顶点更容易落入它的邻域；同时选 $t$ 个顶点再取公共邻域，会把这种偏好放大到 $t$ 次方。于是高共邻结构被保留，孤立的偶然边迅速消失。所得集合起初仍可能含少数“坏”的 $r$ 元组，方法再为每个坏组删掉一个顶点，用很小的规模损失换取对所有剩余 $r$ 元组的统一保证。

名称中的“依赖”指最终选出的顶点通过共享随机样本而相关，并非先假设原图边独立。输入图可以完全确定；随机性只存在于证明过程。它是概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。：正期望证明某次抽样必成功，却不声称任意抽样都成功。

引理证明 ​

从 $V(G)$ 独立均匀、有放回地取 $t$ 个顶点组成多重集 $T$，令 $A=N(T)$。对每个顶点 $v$，事件 $v\in A$ 的概率为 $(d(v)/n{)}^t$。凸性给出

令 $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$ 侧邻点。这个轨迹展示抽样对象是共同邻域，而不是随机保留边。

DRC 不保证 $U$ 的诱导子图稠密，也不自动控制超过 $r$ 个顶点的共同邻域。参数条件可能给不出正的 $a$；此时引理没有结论，不能把期望下界四舍五入成存在大集合。删除坏组的版本只保规模与共邻性质，若还要度数均匀、嵌入计数或算法效率，需要更强的迭代、嵌套或确定化版本。

有了“每个小子集都有许多共邻点”，可以按一侧顶点的顺序贪心嵌入二分图：每放入一个新顶点，都从尚未耗尽的共同邻域选像。由此可证明一侧最大度有界的固定二分图拥有 $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 可沿用这一尺度，把“平均有许多共邻”精炼成一个子集中“每个小组都有许多共邻”，再完成复杂嵌入。后者提供更强的局部一致性，但通常只给足以应用的常数与幂次，不替代具体 Zarankiewicz 问题中的精确计数。