[proofplan]
We verify that $k$-regularity forces Hall's condition and then invoke Hall's Marriage Theorem. Given $A \subseteq X$, we count the edges incident to $A$ (equivalently, the edges of the bipartite subgraph induced by $A$ and $N(A)$) in two ways: summing degrees from the $A$-side gives exactly $k|A|$, while summing degrees from the $N(A)$-side gives at most $k|N(A)|$ because each vertex in $N(A)$ has total degree $k$ (some of whose edges may reach outside $A$). Equating the two counts yields $|A| \leq |N(A)|$. Hall's theorem then delivers the matching.
[/proofplan]
[step:Reduce the problem to verifying Hall's condition]
By [Hall's Marriage Theorem](/theorems/2018), a bipartite graph $G = (X \sqcup Y, E)$ admits a matching from $X$ to $Y$ if and only if
\begin{align*}
|A| \leq |N(A)| \quad \text{for all } A \subseteq X.
\end{align*}
It therefore suffices to verify this condition for our $k$-regular bipartite graph.
[/step]
[step:Count edges between $A$ and $N(A)$ from the $A$-side]
Fix $A \subseteq X$. If $A = \varnothing$ the inequality $0 \leq |N(\varnothing)|$ holds immediately, so assume $A \neq \varnothing$. Let
\begin{align*}
E_A := \{\{x, y\} \in E : x \in A\}
\end{align*}
be the set of edges of $G$ incident to $A$. Because $G$ is bipartite with parts $X$ and $Y$, every edge incident to $x \in A$ has its other endpoint in $Y$, and by definition that endpoint lies in $N(x) \subseteq N(A)$. Summing degrees across $A$:
\begin{align*}
|E_A| = \sum_{x \in A} \deg_G(x) = \sum_{x \in A} k = k|A|,
\end{align*}
where the second equality uses $k$-regularity, $\deg_G(x) = k$ for every $x \in X$.
[/step]
[step:Count the same edges from the $N(A)$-side and bound]
Every edge in $E_A$ has its $Y$-endpoint in $N(A)$, so
\begin{align*}
E_A \subseteq \{\{x, y\} \in E : y \in N(A)\}.
\end{align*}
Counting edges from the $N(A)$-side, each vertex $v \in N(A)$ contributes $\deg_G(v) = k$ total edges, some of which go to $X \setminus A$ and are not in $E_A$. Therefore
\begin{align*}
|E_A| \leq \sum_{v \in N(A)} \deg_G(v) = \sum_{v \in N(A)} k = k|N(A)|,
\end{align*}
using $k$-regularity again, $\deg_G(v) = k$ for every $v \in Y$.
[guided]
We are double-counting the edges incident to $A$. From the $A$-side, every one of $x$'s $k$ edges is incident to $A$ (because $x \in A$), so the count is exactly $k|A|$. From the $N(A)$-side, a vertex $v \in N(A)$ has $k$ total edges but only *some* of them reach $A$ — the others go to vertices of $X \setminus A$ and do not belong to $E_A$. That produces the inequality rather than an equality:
\begin{align*}
|E_A| = k|A|, \qquad |E_A| \leq k|N(A)|.
\end{align*}
**Why the inequality cannot be sharpened.** If every vertex of $N(A)$ had all its edges going to $A$, we would get equality $|E_A| = k|N(A)|$. But in general some edges of $v \in N(A)$ may leave $A$, e.g. if $v$ has neighbours in both $A$ and $X \setminus A$. Those edges contribute to $\deg_G(v) = k$ but not to $|E_A|$, hence $|E_A| \leq k|N(A)|$.
[/guided]
[/step]
[step:Combine the two counts to obtain Hall's condition and conclude]
Combining the equality and inequality from the two counts:
\begin{align*}
k|A| = |E_A| \leq k|N(A)|.
\end{align*}
Dividing both sides by $k > 0$ (valid since $k \geq 1$):
\begin{align*}
|A| \leq |N(A)|.
\end{align*}
Since $A \subseteq X$ was arbitrary, Hall's condition holds, and [Hall's Marriage Theorem](/theorems/2018) yields a matching from $X$ to $Y$.
[/step]
