[proofplan] We verify Hall's condition directly using a double-counting argument on edges. For any subset $S \subseteq X$, we count the edges between $S$ and its neighbourhood $\Gamma(S)$ from both sides. Counting from the $S$-side gives a lower bound of $k|S|$ (since every vertex in $X$ has degree $k$), and counting from the $\Gamma(S)$-side gives an upper bound of $\ell|\Gamma(S)|$ (since every vertex in $Y$ has degree $\ell$). Combining these with $\ell \leq k$ yields $|\Gamma(S)| \geq |S|$, so Hall's condition is satisfied and [Hall's Marriage Theorem](/theorems/2018) produces the complete matching. [/proofplan] [step:Count edges from the $S$-side to establish a lower bound on $e(S, \Gamma(S))$] Let $G = (X, Y; E)$ be $(k, \ell)$-regular with $1 \leq \ell \leq k$. Fix an arbitrary subset $S \subseteq X$ and set $T := \Gamma(S)$, the set of all vertices in $Y$ adjacent to at least one vertex in $S$. Let $e(S, T)$ denote the number of edges with one endpoint in $S$ and the other in $T$. Every vertex $x \in S$ has degree $d(x) = k$ in $G$, and every neighbour of $x$ lies in $Y$. Since $T = \Gamma(S)$ contains all neighbours of every vertex in $S$, every edge incident to a vertex of $S$ has its other endpoint in $T$. Summing over $S$: \begin{align*} e(S, T) = \sum_{x \in S} d(x) = k|S|. \end{align*} [guided] We want to show that $|\Gamma(S)| \geq |S|$ for every $S \subseteq X$, which is Hall's condition. The strategy is to relate $|S|$ and $|\Gamma(S)|$ through the number of edges between them, using the regularity assumption to convert edge counts into vertex counts. Fix an arbitrary $S \subseteq X$ and write $T = \Gamma(S)$ for its neighbourhood in $Y$. Let $e(S, T)$ count the edges between $S$ and $T$. Since $G$ is $(k, \ell)$-regular, every vertex $x \in S$ has exactly $k$ neighbours, all of which lie in $Y$. Moreover, every neighbour of $x$ belongs to $T = \Gamma(S)$ by definition. So every edge incident to $x$ contributes exactly once to $e(S, T)$, and summing over all vertices in $S$ gives: \begin{align*} e(S, T) = \sum_{x \in S} d(x) = \sum_{x \in S} k = k|S|. \end{align*} This is an exact count, not merely a bound: the edges incident to $S$ partition perfectly into one contribution per vertex of $S$, each contributing degree $k$. [/guided] [/step] [step:Count edges from the $\Gamma(S)$-side to establish an upper bound on $e(S, \Gamma(S))$] Each vertex $y \in T = \Gamma(S)$ has degree $d(y) = \ell$ in $G$, and all $\ell$ of its neighbours lie in $X$. However, not all of those neighbours need lie in $S$ — some may lie in $X \setminus S$. Therefore the number of edges from $y$ to $S$ is at most $d(y) = \ell$. Summing over $T$: \begin{align*} e(S, T) \leq \sum_{y \in T} d(y) = \ell|T| = \ell|\Gamma(S)|. \end{align*} [guided] Now we count the same set of edges from the other side. Each vertex $y \in T$ has exactly $\ell$ neighbours in $X$ (by $\ell$-regularity on the $Y$-side), but some of those neighbours may lie outside $S$. So the number of edges from $y$ into $S$ satisfies: \begin{align*} |\{x \in S : xy \in E\}| \leq d(y) = \ell. \end{align*} Summing over all $y \in T$: \begin{align*} e(S, T) = \sum_{y \in T} |\{x \in S : xy \in E\}| \leq \sum_{y \in T} \ell = \ell|T| = \ell|\Gamma(S)|. \end{align*} Why is this only an inequality rather than an equality? Because $T = \Gamma(S)$ may contain vertices whose neighbours in $X$ are not entirely contained in $S$. If $y \in T$ has some neighbours in $X \setminus S$, those edges do not contribute to $e(S, T)$, so the count from the $T$-side overcounts relative to $e(S, T)$. [/guided] [/step] [step:Combine the two edge counts to verify Hall's condition] From the previous two steps: \begin{align*} k|S| = e(S, T) \leq \ell|\Gamma(S)|. \end{align*} Since $\ell \geq 1$, we may divide both sides by $\ell$ to obtain: \begin{align*} |\Gamma(S)| \geq \frac{k}{\ell}|S| \geq |S|, \end{align*} where the second inequality uses $k \geq \ell$. Since $S \subseteq X$ was arbitrary, Hall's condition $|\Gamma(S)| \geq |S|$ holds for every subset of $X$. [guided] Combining the exact lower bound from counting on the $S$-side with the upper bound from counting on the $T$-side: \begin{align*} k|S| = e(S, T) \leq \ell|\Gamma(S)|. \end{align*} Since $\ell \geq 1$ (by hypothesis), we can divide both sides by $\ell$: \begin{align*} |\Gamma(S)| \geq \frac{k}{\ell}|S|. \end{align*} Now we use the assumption $k \geq \ell$, which gives $k/\ell \geq 1$, and therefore: \begin{align*} |\Gamma(S)| \geq \frac{k}{\ell}|S| \geq 1 \cdot |S| = |S|. \end{align*} Since $S \subseteq X$ was an arbitrary subset, we have verified Hall's condition: $|\Gamma(S)| \geq |S|$ for all $S \subseteq X$. Note that the bound is strictly stronger than Hall's condition requires — we have $|\Gamma(S)| \geq (k/\ell)|S|$, so the neighbourhood of any subset of $X$ is at least $k/\ell$ times as large as the subset itself. When $k > \ell$, this gives strict expansion. When $k = \ell$ (the $k$-regular case), we recover Hall's condition with equality possible. [/guided] [/step] [step:Apply Hall's Marriage Theorem to obtain the complete matching] The bipartite graph $G = (X, Y; E)$ satisfies Hall's condition. [Hall's Marriage Theorem](/theorems/2018) states that a bipartite graph has a complete matching from $X$ to $Y$ if and only if $|\Gamma(S)| \geq |S|$ for all $S \subseteq X$. Since this condition holds, $G$ has a complete matching from $X$ to $Y$. [guided] We have established that $|\Gamma(S)| \geq |S|$ for every $S \subseteq X$. [Hall's Marriage Theorem](/theorems/2018) states that a bipartite graph $G = (X, Y; E)$ has a complete matching from $X$ to $Y$ if and only if Hall's condition holds, i.e., $|\Gamma(S)| \geq |S|$ for all $S \subseteq X$. We have verified the condition, so the theorem applies and $G$ has a complete matching from $X$ to $Y$. It is worth noting why we proved this from Hall's theorem directly rather than simply citing the [Degree Condition for Complete Matching](/theorems/2580). The degree condition theorem handles the more general case where $d(x) \geq d(y)$ without requiring regularity, and its proof uses the same double-counting argument we gave here. In the regular case the argument simplifies: the lower bound on $e(S, T)$ becomes an exact count $k|S|$, and the regularity makes the upper bound $\ell|\Gamma(S)|$ transparent. The direct argument also reveals the expansion factor $k/\ell$, which is used in the [Biregular Expansion](/theorems/2582) theorem. [/guided] [/step]