图论技术问题：判定V₁×V₂的边数是否满足指定下界

嘿，这个问题我们可以从邻边计数的角度来拆解，先明确问题前提：

给定简单图$G$，顶点子集$V_1,V_2\subseteq V[G]$（允许两个子集相交），定义$E[V_1\times V_2] = {{x,y}\in E[G]: x\in V_1, y\in V_2 }$。已知对所有$v_1\in V_1$，$|N_E(v_1)\cap V_2|\ge d$（$d$是给定的正整数），求$|E[V_1\times V_2]|$的下界。

核心结论 #

我们可以得到两个实用的下界：

• 通用紧下界：
  $$|E[V_1\times V_2]| \ge \frac{d|V_1|}{2}$$
  这个下界是可以达到的——比如当$V_1=V_2$，且$G[V_1]$是一个$d$-正则图时，等号就成立。

• 更精确的下界（考虑子集交集）：
  我们通过统计所有$V_1$中顶点在$V_2$内的邻边总数来推导：

  1. 记$S = \sum_{v_1\in V_1} |N_E(v_1)\cap V_2|$，根据题设条件，显然$S \ge d|V_1|$。
  2. 观察$S$的构成：
     • 对于$E[V_1\times V_2]$中那些两个端点都在$V_1\cap V_2$的边，每条会被$S$计算两次（因为两个端点都属于$V_1$，都会把对方算入自己的邻点）；
     • 对于仅一个端点在$V_1$的边（另一个端点在$V_2\setminus V_1$），每条只会被$S$计算一次。
  3. 由此可以推出$S = |E[V_1\times V_2]| + |E[V_1\cap V_2]|$（其中$E[V_1\cap V_2]$是$V_1$和$V_2$交集内部的边集）。

  把$S\ge d|V_1|$代入上式，就能得到：
  $$|E[V_1\times V_2]| \ge d|V_1| - |E[V_1\cap V_2]|$$

  这个下界更精准，比如当$V_1$和$V_2$完全不相交时，$|E[V_1\cap V_2]|=0$，此时下界就简化为$|E[V_1\times V_2]|\ge d|V_1|$，这和我们的直观预期完全一致——每个$V_1$中的点至少连$d$条到$V_2$的边，且没有重复计数的情况。

补充说明 #

因为边数不可能为负数，所以实际应用中我们需要取上述结果和0中的较大值，但在题设的条件下（每个$V_1$中的点在$V_2$中至少有$d$个邻点），$S\ge d|V_1|\ge0$，所以对应的下界也不会出现负数的情况。

内容的提问来源于stack exchange，提问作者Connor