[proofplan]
We establish the proportional expansion bound $|\Gamma(A)|/|Y| \geq |A|/|X|$ in two steps. First, a double-counting argument on the edges from $A$ to $\Gamma(A)$ yields $|\Gamma(A)| \geq (k/\ell)|A|$. Second, a global edge count gives the identity $k|X| = \ell|Y|$, which converts the factor $k/\ell$ into $|Y|/|X|$.
[/proofplan]
[step:Bound $|\Gamma(A)|$ from below by double counting edges from $A$]
Let $A \subseteq X$. Every vertex $x \in A$ has degree $k$ in $G$, and all its neighbours lie in $\Gamma(A) \subseteq Y$. Counting edges from the $A$-side:
\begin{align*}
e(A, \Gamma(A)) = k|A|.
\end{align*}
Each vertex $y \in \Gamma(A)$ has degree $\ell$ in $G$, and at most $\ell$ of its edges connect to vertices in $A$. Counting edges from the $\Gamma(A)$-side:
\begin{align*}
e(A, \Gamma(A)) \leq \ell \, |\Gamma(A)|.
\end{align*}
Combining these two counts:
\begin{align*}
k|A| \leq \ell \, |\Gamma(A)|, \quad \text{so} \quad |\Gamma(A)| \geq \frac{k}{\ell} |A|.
\end{align*}
[guided]
We fix an arbitrary subset $A \subseteq X$ and count the edges $e(A, \Gamma(A))$ between $A$ and its neighbourhood $\Gamma(A)$ in two ways.
**From the $A$-side.** Since $G$ is $(k, \ell)$-regular, every vertex $x \in A$ has exactly $k$ neighbours, all in $Y$. By definition of $\Gamma(A)$, every neighbour of every $x \in A$ lies in $\Gamma(A)$. So the count is exact: $e(A, \Gamma(A)) = \sum_{x \in A} k = k|A|$.
**From the $\Gamma(A)$-side.** Each vertex $y \in \Gamma(A)$ has exactly $\ell$ edges in total (by $\ell$-regularity on $Y$), and some of these edges go to vertices in $A$ while others go to $X \setminus A$. So $y$ contributes at most $\ell$ edges to $e(A, \Gamma(A))$. Summing: $e(A, \Gamma(A)) \leq \sum_{y \in \Gamma(A)} \ell = \ell |\Gamma(A)|$.
**Combining.** The chain $k|A| = e(A, \Gamma(A)) \leq \ell |\Gamma(A)|$ gives $|\Gamma(A)| \geq (k/\ell)|A|$ after dividing by $\ell > 0$ (using $\ell \geq 1$).
[/guided]
[/step]
[step:Convert the ratio $k/\ell$ to $|Y|/|X|$ via a global edge count]
Count the total number of edges $|E|$ in two ways. From the $X$-side: each of the $|X|$ vertices has degree $k$, so $|E| = k|X|$. From the $Y$-side: each of the $|Y|$ vertices has degree $\ell$, so $|E| = \ell|Y|$. Equating:
\begin{align*}
k|X| = \ell|Y|, \quad \text{so} \quad \frac{k}{\ell} = \frac{|Y|}{|X|}.
\end{align*}
[guided]
The global edge count is a standard consequence of biregularity. Every vertex $x \in X$ contributes $k$ edges and every vertex $y \in Y$ contributes $\ell$ edges. Since every edge is counted once from each side, we get $k|X| = |E| = \ell|Y|$. Rearranging gives $k/\ell = |Y|/|X|$.
This identity is the link between the local degree structure and the global size ratio. It says that the degree imbalance $k/\ell$ is exactly compensated by the size ratio $|Y|/|X|$: the side with higher degree must have fewer vertices.
[/guided]
[/step]
[step:Combine to obtain the proportional expansion bound]
Substituting $k/\ell = |Y|/|X|$ into the bound $|\Gamma(A)| \geq (k/\ell)|A|$:
\begin{align*}
|\Gamma(A)| \geq \frac{|Y|}{|X|} |A|.
\end{align*}
Dividing both sides by $|Y|$:
\begin{align*}
\frac{|\Gamma(A)|}{|Y|} \geq \frac{|A|}{|X|}.
\end{align*}
This holds for every $A \subseteq X$, completing the proof.
[/step]
