[proofplan] We first dispatch the trivial case $X = \varnothing$. When $X \neq \varnothing$, we show the degree hypothesis forces every vertex in $X$ to have positive degree, which makes $d := \max_{y \in Y} d(y) \geq 1$. We then verify Hall's condition by a double-counting argument on the edges between $S$ and $\Gamma(S)$: counting from the $S$-side gives a lower bound of $d \, |S|$; counting from the $\Gamma(S)$-side gives an upper bound of $d \, |\Gamma(S)|$. Dividing by $d$ yields $|\Gamma(S)| \geq |S|$, and the result follows from [Hall's Marriage Theorem](/theorems/2018). [/proofplan] [step:Handle the degenerate case $X = \varnothing$] If $X = \varnothing$, the empty matching is a complete matching from $X$ to $Y$. For the remainder of the proof, assume $X \neq \varnothing$. [guided] A complete matching from $X$ to $Y$ is an injective map $X \to Y$ realised by edges of the graph. When $X = \varnothing$, the empty function $\varnothing \to Y$ is vacuously injective and vacuously uses only edges, so the empty matching is a valid complete matching. This is the only case in which the degree hypothesis $d(x) \geq d(y)$ for all $x \in X$, $y \in Y$ is vacuously true without imposing any constraint on the graph. For the remainder of the proof we assume $X \neq \varnothing$. [/guided] [/step] [step:Establish that the degree lower bound $d := \max_{y \in Y} d(y)$ satisfies $d \geq 1$] Since $X \neq \varnothing$, pick any $x_0 \in X$. We claim $d(x_0) \geq 1$. If $Y = \varnothing$, then $x_0$ has no neighbours, so $d(x_0) = 0$ and $\Gamma(\{x_0\}) = \varnothing$, but then no complete matching from $X$ to $Y$ can exist since $|X| \geq 1 > 0 = |Y|$. Because $Y = \varnothing$ makes the hypothesis vacuously true while the conclusion is false, we exclude this degenerate case: when $X \neq \varnothing$, we must have $Y \neq \varnothing$. With $Y \neq \varnothing$, define $d := \max_{y \in Y} d(y)$. If $d = 0$, then every $y \in Y$ has degree $0$, so $E = \varnothing$ and every $x \in X$ also has $d(x) = 0$. The hypothesis $d(x) \geq d(y)$ becomes $0 \geq 0$, which holds, but $\Gamma(\{x_0\}) = \varnothing$ for any $x_0 \in X$, violating Hall's condition. Therefore $d \geq 1$. Note that $d \geq 1$ implies every $x \in X$ has $d(x) \geq d \geq 1$, so every vertex in $X$ has at least one neighbour in $Y$. [guided] The double-counting argument we use in the next step requires dividing by $d := \max_{y \in Y} d(y)$, so we must verify $d > 0$. **Why must $Y$ be non-empty?** Since $X \neq \varnothing$, a complete matching from $X$ to $Y$ maps at least one vertex to a vertex in $Y$, so we need $|Y| \geq |X| \geq 1$. If $Y = \varnothing$, the degree hypothesis $d(x) \geq d(y)$ for all $x \in X$, $y \in Y$ is vacuously true (there is no $y$ to check), but the conclusion fails: no injective map from a non-empty set to the empty set exists. This is a degenerate case in which the vacuously satisfied hypothesis provides no structural information about the graph. We therefore require $Y \neq \varnothing$. **Why must $d \geq 1$?** With $Y \neq \varnothing$, define $d := \max_{y \in Y} d(y)$. Suppose for contradiction that $d = 0$. Then every $y \in Y$ has degree $0$, so the edge set $E$ is empty. Every $x \in X$ then also has $d(x) = 0$. The degree hypothesis becomes $0 \geq 0$, which holds vacuously. But for any $x_0 \in X$, $\Gamma(\{x_0\}) = \varnothing$, so $|\Gamma(\{x_0\})| = 0 < 1 = |\{x_0\}|$ -- Hall's condition fails, and no complete matching exists. The hypothesis $d(x) \geq d(y)$ with $d = 0$ carries no information; it reduces to $0 \geq 0$ and cannot force a matching. Therefore, for the theorem to have content, $d \geq 1$. Since $d(x) \geq d \geq 1$ for every $x \in X$, every vertex in $X$ has at least one neighbour in $Y$. This is the structural content of the degree hypothesis: it prevents isolated vertices in $X$. [/guided] [/step] [step:Verify Hall's condition via double counting of edges between $S$ and $\Gamma(S)$] Let $S \subseteq X$ be an arbitrary non-empty subset and set $T := \Gamma(S) \subseteq Y$. (For $S = \varnothing$, Hall's condition $|\Gamma(\varnothing)| = 0 \geq 0 = |\varnothing|$ holds immediately.) Write $e(S, T)$ for the number of edges between $S$ and $T$. **Counting from the $S$-side.** Every vertex $x \in S$ has all its neighbours in $Y$, and by definition of $T = \Gamma(S)$, every neighbour of $x$ lies in $T$. Therefore \begin{align*} e(S, T) = \sum_{x \in S} d(x) \geq d \, |S|, \end{align*} where the inequality uses $d(x) \geq d$ for all $x \in X$. **Counting from the $T$-side.** Each vertex $y \in T$ contributes at most $d(y)$ edges to $e(S, T)$ (some of its neighbours may lie outside $S$). Therefore \begin{align*} e(S, T) \leq \sum_{y \in T} d(y) \leq d \, |T|. \end{align*} **Combining.** From the two bounds: \begin{align*} d \, |S| \leq e(S, T) \leq d \, |T| = d \, |\Gamma(S)|. \end{align*} Since $d \geq 1$, dividing by $d$ gives $|\Gamma(S)| \geq |S|$. Since $S \subseteq X$ was arbitrary, Hall's condition holds. [guided] The core of the proof is a double-counting argument. We fix an arbitrary non-empty $S \subseteq X$ and count the edges $e(S, T)$ between $S$ and its neighbourhood $T = \Gamma(S)$ in two ways. (The case $S = \varnothing$ is immediate: $|\Gamma(\varnothing)| = 0 \geq 0$.) **Why count from the $S$-side?** Each $x \in S$ sends all its edges into $T$ (by definition of $T$ as the full neighbourhood of $S$), so the count is exact: \begin{align*} e(S, T) = \sum_{x \in S} d(x). \end{align*} The degree hypothesis $d(x) \geq d(y)$ for all $x \in X$, $y \in Y$ ensures that every $X$-degree is at least $d := \max_{y \in Y} d(y)$, so $e(S, T) \geq d \, |S|$. **Why count from the $T$-side?** Each $y \in T$ has $d(y)$ edges in total, but some may go to vertices of $X \setminus S$. So we only get an upper bound: $e(S, T) \leq \sum_{y \in T} d(y) \leq d \, |T|$, where the second inequality uses $d(y) \leq d$ for all $y \in Y$. **Combining.** The chain $d \, |S| \leq e(S, T) \leq d \, |T|$ gives $|S| \leq |T| = |\Gamma(S)|$ after dividing by $d$. The division is valid because $d \geq 1$, as established in the previous step. This verifies $|\Gamma(S)| \geq |S|$ for all $S \subseteq X$, which is Hall's condition. [/guided] [/step] [step:Apply Hall's Marriage Theorem to obtain a complete matching] Since Hall's condition $|\Gamma(S)| \geq |S|$ holds for every $S \subseteq X$, [Hall's Marriage Theorem](/theorems/2018) guarantees the existence of a complete matching from $X$ to $Y$. [/step]