My proof of Hall's Marriage Theorem

Hall's Marriage Theorem: each girl $x\in X$ likes a set of boys $f(x)\subset Y$. We can find an unique boy $m(x)\in f(x)$ for every girl $x$ if and only if
$$
|f(X')|\geq |X'| ~~~~~~~~~(*)
$$
for every $X'\subset X$.

Proof:
Necessary condition is trivial. For sufficient condition, we prove it by induction on $|X|$.

Case 1:
$X$ can be split into disjoint non-empty sets $X_1,X_2$ such that $|f(X_1)|=|X_1|$. So $\left(X_1,f(X_1)\right)$ satisfies (*). We want to show so does $\left(X_2,Y\setminus f(X_1)\right)$: for every $X'\subset X_2$,
$$
|X'|+|X_1|=|X'\cup X_1|\leq |f(X'\cup X_1)|=|X_1|+|f(X')\setminus f(X_1)|
$$
Therefore
$$
|X'|\leq |f(X')\setminus f(X_1)|
$$

and $\left(X_2,Y\setminus f(X_1)\right)$ satisfies (*). By inductive hypothesis on $X_1$ and $X_2$ such $m(\cdot)$ exists.

Case 2:

No such splitting exists, so $|f(X')|\gt |X'|$ for every $X'\subset X$. Pick an element $x_0\in X$ and make $m(x_0)=y_0\in f(x_0)$. Remove $x_0$ and $y_0$ from $X$ and $Y$, respectively. Now $|f(X')|$ decreases by no more than $1$ for every $X'\subset X$, so $|f(X')|\geq |X'|$ and by inductive hypothesis on this reduced $X$ the desired $m(\cdot)$ exists.

Q.E.D.