[proofplan] We prove both directions of the equivalence. The forward direction is immediate: any complete matching witnesses Hall's condition. For the reverse, we use an edge-minimality argument. Among all bipartite graphs on $X \sqcup Y$ satisfying Hall's condition, we take one with the fewest edges and show it must already be a complete matching. The combinatorial core is a counting argument: if any vertex in $Y$ had degree $\geq 2$, removing either edge would produce a tight set, and the two tight sets would contradict Hall's condition on their intersection. [/proofplan] [step:Verify that any complete matching implies Hall's condition] Suppose $f: X \to Y$ is a complete matching. Let $S \subseteq X$ be an arbitrary subset. Since $f$ is injective and $f(x) \in \Gamma(S)$ for every $x \in S$, the set $\{f(x) : x \in S\} \subseteq \Gamma(S)$ has cardinality $|S|$. Therefore $|\Gamma(S)| \geq |S|$ for every $S \subseteq X$, which is Hall's condition. [guided] The forward direction asks: if we already have a complete matching $f: X \to Y$, must Hall's condition hold? A complete matching is an injection $f: X \to Y$ with $xf(x) \in E$ for every $x \in X$. Take any subset $S \subseteq X$. Each $x \in S$ has $f(x) \in \Gamma(S)$ because $xf(x)$ is an edge. Moreover, the elements $f(x)$ for $x \in S$ are all distinct because $f$ is injective. So $\Gamma(S)$ contains the set $\{f(x) : x \in S\}$, which has exactly $|S|$ elements. Hence $|\Gamma(S)| \geq |S|$. This must hold for every $S \subseteq X$ simultaneously, since the same matching $f$ witnesses the bound for all subsets at once. [/guided] [/step] [step:Reduce to the edge-minimal graph satisfying Hall's condition] Now assume Hall's condition holds. Among all bipartite graphs on vertex set $X \sqcup Y$ satisfying Hall's condition, choose one with the fewest edges and call it $G$. We will show that $G$ is itself a complete matching. [guided] The strategy for the reverse direction is a minimality argument rather than an explicit construction. We do not build a matching greedily or use augmenting paths. Instead, we consider the collection of all bipartite graphs on the fixed vertex set $X \sqcup Y$ that satisfy Hall's condition. This collection is non-empty (it contains our given graph). Among all such graphs, pick one with the minimum number of edges. We will deduce that this edge-minimal graph has such a constrained structure that it must be a complete matching: every vertex in $X$ has degree exactly $1$ and every vertex in $Y$ has degree at most $1$. Why does minimality help? Because if $G$ has any "unnecessary" edge, we could remove it and still satisfy Hall's condition, contradicting the choice of $G$. So every edge of $G$ is critical, and this severely restricts the degree sequence. [/guided] [/step] [step:Show every vertex of $Y$ has degree at most $1$ in the minimal graph] Suppose for contradiction that some $y \in Y$ has two neighbours $x_1, x_2 \in X$. Since $G$ is edge-minimal, removing the edge $x_1 y$ violates Hall's condition: there exists $X_1 \subseteq X$ with $x_1 \in X_1$ such that in the graph $G - x_1 y$, the neighbourhood $\Gamma_{G - x_1 y}(X_1)$ satisfies $|\Gamma_{G - x_1 y}(X_1)| < |X_1|$. Since $G$ itself satisfies Hall's condition, the only vertex lost from $\Gamma_G(X_1)$ is $y$, and the inequality is tight: \begin{align*} |\Gamma_G(X_1)| = |X_1|, \quad \text{and } x_1 \text{ is the unique neighbour of } y \text{ in } X_1. \end{align*} By the same argument applied to the edge $x_2 y$, there exists $X_2 \subseteq X$ with $x_2 \in X_2$ such that \begin{align*} |\Gamma_G(X_2)| = |X_2|, \quad \text{and } x_2 \text{ is the unique neighbour of } y \text{ in } X_2. \end{align*} Now consider $X_1 \cap X_2$. Since $x_1$ is the unique neighbour of $y$ in $X_1$ and $x_2$ is the unique neighbour of $y$ in $X_2$, and $x_1 \neq x_2$, at most one of $x_1, x_2$ lies in $X_1 \cap X_2$. Therefore $y \notin \Gamma_G(X_1 \cap X_2)$. But $y \in \Gamma_G(X_1) \cap \Gamma_G(X_2)$, so the inclusion $\Gamma_G(X_1 \cap X_2) \subseteq \Gamma_G(X_1) \cap \Gamma_G(X_2)$ is strict: \begin{align*} |\Gamma_G(X_1 \cap X_2)| \leq |\Gamma_G(X_1) \cap \Gamma_G(X_2)| - 1. \end{align*} Applying inclusion-exclusion and the identity $\Gamma_G(X_1) \cup \Gamma_G(X_2) = \Gamma_G(X_1 \cup X_2)$: \begin{align*} |X_1 \cap X_2| &\leq |\Gamma_G(X_1 \cap X_2)| \\ &\leq |\Gamma_G(X_1) \cap \Gamma_G(X_2)| - 1 \\ &= |\Gamma_G(X_1)| + |\Gamma_G(X_2)| - |\Gamma_G(X_1) \cup \Gamma_G(X_2)| - 1 \\ &= |X_1| + |X_2| - |\Gamma_G(X_1 \cup X_2)| - 1 \\ &\leq |X_1| + |X_2| - |X_1 \cup X_2| - 1 \\ &= |X_1 \cap X_2| - 1. \end{align*} The first inequality is Hall's condition applied to $X_1 \cap X_2$. The fourth line substitutes $|\Gamma_G(X_1)| = |X_1|$ and $|\Gamma_G(X_2)| = |X_2|$. The fifth inequality applies Hall's condition to $X_1 \cup X_2$. The final equality is inclusion-exclusion for $|X_1| + |X_2| - |X_1 \cup X_2|$. We obtain $|X_1 \cap X_2| \leq |X_1 \cap X_2| - 1$, a contradiction. [guided] This is the combinatorial heart of the proof. Suppose some vertex $y \in Y$ has at least two neighbours $x_1, x_2 \in X$. We will derive a contradiction from edge-minimality. **Producing the tight sets.** Since $G$ is edge-minimal among graphs satisfying Hall's condition, deleting any single edge must break Hall's condition. Deleting the edge $x_1 y$ breaks it, so there is a subset $X_1 \subseteq X$ whose neighbourhood shrinks below $|X_1|$ when we remove $x_1 y$. In the original graph $G$, Hall's condition gives $|\Gamma_G(X_1)| \geq |X_1|$; after deleting $x_1 y$ the neighbourhood drops, so the only vertex lost must be $y$ itself, and the set $X_1$ must have been exactly tight: $|\Gamma_G(X_1)| = |X_1|$. Moreover, $y$ was connected to $X_1$ only through $x_1$ (otherwise removing the edge $x_1 y$ would not remove $y$ from $\Gamma(X_1)$). Symmetrically, deleting $x_2 y$ yields a tight set $X_2$ with $|\Gamma_G(X_2)| = |X_2|$ where $x_2$ is the unique neighbour of $y$ in $X_2$. **Why their intersection causes trouble.** Since $x_1$ is $y$'s only neighbour in $X_1$ and $x_2$ is $y$'s only neighbour in $X_2$, and $x_1 \neq x_2$, at most one of them lies in $X_1 \cap X_2$. So $y$ has no neighbour in $X_1 \cap X_2$ (if $x_1 \in X_1 \cap X_2$ then $x_1 \in X_2$, but $x_2$ is $y$'s unique neighbour in $X_2$, so $x_1 = x_2$, contradicting $x_1 \neq x_2$; similarly for $x_2$). Therefore $y \notin \Gamma_G(X_1 \cap X_2)$, even though $y \in \Gamma_G(X_1) \cap \Gamma_G(X_2)$. **The counting contradiction.** We chain inequalities. Hall's condition on $X_1 \cap X_2$ gives the first line. The strict exclusion of $y$ gives the second. Inclusion-exclusion and the tightness $|\Gamma_G(X_i)| = |X_i|$ complete the chain: \begin{align*} |X_1 \cap X_2| &\leq |\Gamma_G(X_1 \cap X_2)| \\ &\leq |\Gamma_G(X_1) \cap \Gamma_G(X_2)| - 1 \\ &= |\Gamma_G(X_1)| + |\Gamma_G(X_2)| - |\Gamma_G(X_1) \cup \Gamma_G(X_2)| - 1 \\ &= |X_1| + |X_2| - |\Gamma_G(X_1 \cup X_2)| - 1 \\ &\leq |X_1| + |X_2| - |X_1 \cup X_2| - 1 \\ &= |X_1 \cap X_2| - 1. \end{align*} This says $|X_1 \cap X_2| \leq |X_1 \cap X_2| - 1$, which is impossible. The identity $\Gamma_G(X_1) \cup \Gamma_G(X_2) = \Gamma_G(X_1 \cup X_2)$ holds because any neighbour of a vertex in $X_1 \cup X_2$ is a neighbour of a vertex in $X_1$ or $X_2$. The last line uses inclusion-exclusion for sets: $|X_1| + |X_2| - |X_1 \cup X_2| = |X_1 \cap X_2|$. The essential structure of this contradiction is that two tight sets whose intersection loses a common neighbour cannot coexist under Hall's condition. [/guided] [/step] [step:Show every vertex of $X$ has degree exactly $1$ in the minimal graph] No vertex $x \in X$ can have degree $0$: taking $S = \{x\}$ gives $|\Gamma(\{x\})| = 0 < 1 = |S|$, violating Hall's condition. Suppose some $x \in X$ has degree $\geq 2$, say $x$ is adjacent to $y_1$ and $y_2$. By the previous step, each $y_i$ has degree exactly $1$ in $G$, so $y_i$ is adjacent only to $x$. Remove the edge $xy_1$. For any $S \subseteq X$ with $x \notin S$, the neighbourhood $\Gamma(S)$ is unchanged. For any $S \subseteq X$ with $x \in S$, the vertex $y_1$ is no longer in $\Gamma(S)$ via $x$, but since $y_1$ has degree $1$, the only vertex in $S$ adjacent to $y_1$ was $x$; however, $x$ still has $y_2 \in \Gamma(S)$, and the neighbourhood of $S$ loses at most $y_1$. Meanwhile, from the previous step, every vertex of $Y$ has degree at most $1$, so $y_1$ was only reachable from $x$. Therefore $|\Gamma_{G - xy_1}(S)| \geq |\Gamma_G(S)| - 1$. But $|\Gamma_G(S)| \geq |S|$ and $y_2$ is still in $\Gamma_{G - xy_1}(S)$ whenever $x \in S$, so $|\Gamma_{G-xy_1}(S)| \geq |S|$. This contradicts the edge-minimality of $G$. [guided] We already know from the previous step that every vertex of $Y$ has degree at most $1$. Now we show every vertex of $X$ has degree exactly $1$. **Degree $0$ is impossible.** If $x \in X$ has no neighbours, then $\Gamma(\{x\}) = \varnothing$, giving $|\Gamma(\{x\})| = 0 < 1 = |\{x\}|$, which directly violates Hall's condition. **Degree $\geq 2$ contradicts minimality.** Suppose $x \in X$ has at least two neighbours, say $y_1$ and $y_2$. Since every vertex of $Y$ has degree at most $1$ (from the previous step), both $y_1$ and $y_2$ are adjacent only to $x$. Consider deleting the edge $xy_1$ to form $G' = G - xy_1$. We claim Hall's condition still holds in $G'$. Take any $S \subseteq X$. If $x \notin S$, then $\Gamma_{G'}(S) = \Gamma_G(S)$ because the deleted edge is not incident to any vertex of $S$, so $|\Gamma_{G'}(S)| = |\Gamma_G(S)| \geq |S|$. If $x \in S$, then $y_2 \in \Gamma_{G'}(S)$ because the edge $xy_2$ survives. The only vertex that could be lost from $\Gamma_G(S)$ is $y_1$. But since $y_1$ has degree $1$ in $G$ (adjacent only to $x$), we have $y_1 \in \Gamma_G(S)$ only because $x \in S$. In $G'$, the edge $xy_1$ is gone, so $y_1 \notin \Gamma_{G'}(S)$. Thus $\Gamma_{G'}(S) = \Gamma_G(S) \setminus \{y_1\}$, giving $|\Gamma_{G'}(S)| = |\Gamma_G(S)| - 1 \geq |S| - 1$. But we also have $y_2 \in \Gamma_{G'}(S)$, and since $y_2$ has degree $1$ in $G$ (and hence in $G'$, where $y_2$ is still adjacent to $x$), the vertex $y_2$ replaces the role of $y_1$. More precisely, $|\Gamma_G(S)| \geq |S|$ gives us enough room: the neighbourhood $\Gamma_G(S)$ has at least $|S|$ vertices, removing $y_1$ drops it by $1$, but we need $|\Gamma_{G'}(S)| \geq |S|$. Since every vertex of $Y$ has degree at most $1$, the vertices $y_1$ and $y_2$ are distinct elements of $\Gamma_G(\{x\}) \subseteq \Gamma_G(S)$. In $G'$, only $y_1$ is lost, so $\Gamma_{G'}(S)$ still contains $y_2$ and all neighbours of $S \setminus \{x\}$. The count $|\Gamma_{G'}(S)| \geq |\Gamma_G(S)| - 1 \geq |S| - 1$ must be strengthened: note that $\Gamma_G(S)$ must have had $|\Gamma_G(S)| \geq |S|$, and we only removed one element ($y_1$), so $|\Gamma_{G'}(S)| \geq |S| - 1$. But this is not quite enough — we need $\geq |S|$. The sharper argument: since $y_2 \in \Gamma_{G'}(S)$ and $y_2 \notin \Gamma_G(S \setminus \{x\})$ (because $y_2$ has degree $1$, adjacent only to $x$), the vertex $y_2$ is a "private" neighbour of $x$ that survives in $G'$. For any $S$ with $x \in S$: $\Gamma_{G'}(S) \supseteq \Gamma_{G'}(S \setminus \{x\}) \cup \{y_2\}$. By Hall's condition in $G$ (which equals $G'$ for sets not containing $x$), $|\Gamma_{G'}(S \setminus \{x\})| = |\Gamma_G(S \setminus \{x\})| \geq |S| - 1$. Adding $y_2$, which is distinct from all elements of $\Gamma_{G'}(S \setminus \{x\})$ (since $y_2$ has no neighbour in $S \setminus \{x\}$), gives $|\Gamma_{G'}(S)| \geq |S| - 1 + 1 = |S|$. So Hall's condition holds in $G'$, but $G'$ has strictly fewer edges than $G$. This contradicts the edge-minimality of $G$. [/guided] [/step] [step:Conclude that the edge-minimal graph is a complete matching] Every vertex of $X$ has degree exactly $1$ and every vertex of $Y$ has degree at most $1$. The degree-$1$ condition on $X$ means each $x \in X$ is adjacent to exactly one vertex $f(x) \in Y$, defining a function $f: X \to Y$ with $xf(x) \in E$. The degree-at-most-$1$ condition on $Y$ means no two vertices of $X$ share the same neighbour, so $f$ is injective. Therefore $f$ is a complete matching from $X$ to $Y$. [/step]