[proofplan]
We reduce both directions to Hall's Marriage Theorem by introducing or removing $d$ dummy vertices on the $Y$-side. For the converse, we augment $G$ to a bipartite graph $G'$ by adding $d$ dummy vertices each joined to every vertex of $X$; the defect hypothesis $|A| \leq |N(A)| + d$ becomes Hall's condition in $G'$, so Hall's theorem produces a full matching from $X$ in $G'$, and discarding the edges to dummy vertices yields a matching of deficiency at most $d$ in $G$. For the forward direction, we apply Hall's condition to the $|X|-d$ vertices that are already matched and use monotonicity of the neighbourhood.
[/proofplan]
[step:Prove the forward direction by applying Hall's condition on the matched vertex set]
Suppose $G$ admits a matching of deficiency at most $d$. By definition, this is a subset $X' \subseteq X$ with $|X'| \geq |X| - d$ and an injection
\begin{align*}
m: X' &\to Y \\
x &\mapsto m(x)
\end{align*}
with $\{x, m(x)\} \in E$ for every $x \in X'$. Fix $A \subseteq X$ and consider $A \cap X' \subseteq X'$. The restriction $m|_{A \cap X'}$ is an injection from $A \cap X'$ into $N_G(A \cap X') \subseteq N_G(A)$, so
\begin{align*}
|A \cap X'| \leq |N_G(A)|.
\end{align*}
Since $|X'| \geq |X| - d$, at most $d$ vertices of $X$ lie outside $X'$, so
\begin{align*}
|A \cap X'| \geq |A| - d.
\end{align*}
Combining,
\begin{align*}
|A| - d \leq |N_G(A)|,
\end{align*}
which is the defect condition.
[/step]
[step:Construct an augmented bipartite graph $G'$ with $d$ dummy vertices for the converse]
Assume the defect condition $|A| \leq |N(A)| + d$ holds for every $A \subseteq X$. Introduce a set $Z := \{z_1, \ldots, z_d\}$ of $d$ fresh vertices disjoint from $X \cup Y$, and define
\begin{align*}
G' = (X \sqcup (Y \cup Z), E \cup E'), \qquad E' := \{\{x, z_i\} : x \in X,\, i \in [d]\}.
\end{align*}
Thus $G'$ is a bipartite graph with left side $X$ and right side $Y \cup Z$, whose edges are the edges of $G$ together with every possible edge from $X$ to $Z$.
[/step]
[step:Verify Hall's condition in $G'$]
We show $|A| \leq |N_{G'}(A)|$ for every $A \subseteq X$.
If $A = \varnothing$, the inequality $0 \leq |N_{G'}(\varnothing)|$ holds immediately.
If $A \neq \varnothing$, pick any $x_0 \in A$. Every $z_i \in Z$ is adjacent to $x_0$ by construction of $E'$, so $Z \subseteq N_{G'}(x_0) \subseteq N_{G'}(A)$. Moreover $N_{G'}(A) \cap Y = N_G(A)$ because the only new edges in $E'$ go to $Z$. Since $Z \cap Y = \varnothing$, the two parts of $N_{G'}(A)$ are disjoint and
\begin{align*}
|N_{G'}(A)| = |N_G(A)| + |Z| = |N_G(A)| + d.
\end{align*}
Applying the defect hypothesis in $G$,
\begin{align*}
|A| \leq |N_G(A)| + d = |N_{G'}(A)|,
\end{align*}
which is Hall's condition for $G'$.
[guided]
The additional $d$ dummies are there precisely to absorb the "defect" of $d$ that is allowed in the hypothesis. Translating: the defect condition $|A| \leq |N_G(A)| + d$ says that $A$ has at least $|A| - d$ neighbours in $Y$; by joining every $z_i \in Z$ to every vertex of $X$, we make up for the missing $d$ neighbours with $d$ guaranteed ones.
**Why $Z$ must be joined to all of $X$.** For Hall's condition to hold in $G'$ for an arbitrary $A \subseteq X$, the augmentation must contribute exactly $d$ extra neighbours to every non-empty $A$. Joining every $z_i$ to every vertex of $X$ achieves this: any non-empty $A$ picks up all $d$ dummies in its $G'$-neighbourhood.
**Computing $|N_{G'}(A)|$.** The augmentation adds only edges between $X$ and $Z$, so
\begin{align*}
N_{G'}(A) \cap Y = N_G(A), \qquad N_{G'}(A) \cap Z = \begin{cases} Z & A \neq \varnothing \\ \varnothing & A = \varnothing. \end{cases}
\end{align*}
For non-empty $A$, $Y$ and $Z$ are disjoint so
\begin{align*}
|N_{G'}(A)| = |N_G(A)| + d.
\end{align*}
The defect condition $|A| \leq |N_G(A)| + d$ is now literally the Hall inequality for $G'$.
**Edge case $A = \varnothing$.** For the empty set, Hall's inequality reduces to $0 \leq 0$, which holds directly. The $d$ dummies are irrelevant here.
[/guided]
[/step]
[step:Apply Hall's theorem in $G'$ and discard dummy-vertex edges]
Since $G'$ is bipartite with left side $X$ and Hall's condition holds, [Hall's Marriage Theorem](/theorems/2018) produces an injection
\begin{align*}
m': X &\to Y \cup Z \\
x &\mapsto m'(x)
\end{align*}
with $\{x, m'(x)\} \in E(G')$ for every $x \in X$. Let
\begin{align*}
X' := \{x \in X : m'(x) \in Y\},
\end{align*}
and define $m := m'|_{X'}$, so
\begin{align*}
m: X' &\to Y \\
x &\mapsto m'(x).
\end{align*}
**Edges lie in $E$.** For $x \in X'$, the edge $\{x, m'(x)\} \in E(G')$ with $m'(x) \in Y$ cannot be in $E'$ (whose edges have an endpoint in $Z$), so it lies in $E$.
**Injectivity.** The restriction of an injection is an injection.
**Deficiency bound.** The map $m'$ is injective and hits every $z_i \in Z$ at most once, so $|X \setminus X'| = |(m')^{-1}(Z)| \leq |Z| = d$. Hence
\begin{align*}
|X'| = |X| - |X \setminus X'| \geq |X| - d,
\end{align*}
so $m: X' \to Y$ is a matching of deficiency at most $d$ in $G$.
[guided]
Hall's theorem in $G'$ produces an injection $m': X \to Y \cup Z$. The strategy is to keep only the part that lands in the original $Y$: those vertices of $X$ matched to $Y$ are matched in $G$, and the remaining vertices are the deficiency.
**Restricting to real matches.** Let $X' := (m')^{-1}(Y) = \{x \in X : m'(x) \in Y\}$, the subset of $X$ matched to a real (non-dummy) vertex. Restricting $m'$ to $X'$ gives a map into $Y$:
\begin{align*}
m: X' &\to Y \\
x &\mapsto m'(x).
\end{align*}
**Checking the edge condition.** For $x \in X'$, the edge $\{x, m'(x)\} \in E(G')$ has $m'(x) \in Y$. The edges of $G'$ are $E \cup E'$, and every edge in $E'$ has one endpoint in $Z$. Since $m'(x) \notin Z$, the edge must come from $E$. Hence $\{x, m(x)\} \in E$ and $m$ is a matching in $G$.
**Counting the deficiency.** How large is $X \setminus X'$? By definition $X \setminus X' = (m')^{-1}(Z)$, the set of left vertices matched to dummies. Since $m'$ is injective and $|Z| = d$, we have $|(m')^{-1}(Z)| \leq d$. Therefore
\begin{align*}
|X'| = |X| - |(m')^{-1}(Z)| \geq |X| - d,
\end{align*}
which is the defect bound. Combining with the edge condition, $m: X' \to Y$ is a matching of deficiency at most $d$, completing the converse.
[/guided]
[/step]
