Combinatorics

Let $G = \big( V, E \big)$ be a bipartite graph with partitions $\big( U, W \big)$ .

Suppose

$\begin{equation*} d_G(x) \ge r \quad \text{and} \quad d_G(y) \le s, \quad \forall x \in U, y \in W \end{equation*}$

where $r, s \ge 1$ .

Then, for non-empty $A ⊂ U,

$\begin{equation*} \left| \Gamma(A) \right| \ge \frac{r \left| A \right|}{s} \end{equation*}$

Equality holds iff $G$ is (r, s)-regular and $A = U$ .

Let $$$ be the subgraph induced by $A \cup \Gamma(A)$ , then

$\begin{equation*} r \left| A \right| \le e(H) \le s \left| \Gamma(A) \right| \end{equation*}$

where $e(H)$ is the number of edges in