# Proof of Hall's marriage Theorem based on isolated vertex version

We all know the usual Hall theorem as follows:

Theorem (Hall's Theorem, Hall (1935)). Let $$G = (X, Y)$$ be a bipartite graph. Then $$G$$ has a matching saturating all vertices of $$X$$ if and only if for any $$S\subseteq X$$, $$|N(S)|\ge |S|$$.

Furthermore, we have a equivalent characterization of perfect matching of bipartite graphs, that is Marriage Theorem.

Theorem (Marriage Theorem). A bipartite graph $$G$$ with bipartition $$\{X,Y\}$$ has a perfect matching if and only if $$|X|=|Y|$$ and $$|N(S)|\ge |S|$$ for any subset $$S\subseteq X$$ (or $$Y$$).

I read a monograph on matching theory (Yu Q R, Liu G. Graph factors and matching extensions[M]. Springer, 2010.), and I read the following description.

Theorem Let $$G = (X, Y)$$ be a bipartite graph. Then $$G$$ has a perfect matching if and only if $$|X|=|Y|$$ and for any $$S \subseteq X$$, $$i(G-S)\le |S|$$, where $$i(G-S)$$ denotes the number of isolated vertices in $$G-S$$.

I'm curious why this theorem is also an equivalent description of a perfect matching of bipartite graphs.

The proof of the direction of necessity is simply based on the Tutte 1-factor Theorem.

Tutte 1-factor Theorem A graph $$G$$ has a perfect matching iff $$∀S ⊆ V , o(G - S) ≤ |S|$$ where $$o(G − S)$$ denote the number of components of odd cardinality in $$G − S$$.

But the reverse is not so easy to see. Because such an $$S'$$ does exist, some odd component of $$G-S'$$ may be not a isolated vertex.

I have no idea about how to prove the sufficiency of the theorem.

The isolated-vertex condition is equivalent to Hall's condition.

We'll assume that $$G$$ has no isolated vertices. If it does, then both Hall's condition and the isolated vertex condition are easily seen to be violated.

1. Suppose there is a set $$U \subseteq X$$ for which $$i(G-U) > |U|$$. Then let $$S$$ be the set of all isolated vertices in $$G-U$$. We must have $$N(S) \subseteq U$$, because in $$G-U$$, no neighbors of $$S$$ survive. Also, we must have $$S \subseteq Y$$, because deleting a subset of $$X$$ can't isolate a vertex in $$X$$ that wasn't isolated already. So $$S$$ is a violation of Hall's condition (from the $$Y$$ perspective).
2. Suppose there is a set $$S \subseteq Y$$ for which $$|N(S)| < |S|$$. Then let $$U = N(S)$$. In $$G-U$$, all of $$S$$ will be isolated (and maybe more), so $$i(G-U) \ge |S| > |U|$$.

You have already shown that if $$G$$ is bipartite and has a perfect matching, then for all $$S \subseteq V(G)$$, $$i(G - S) \leq |S|$$. We show that if for all $$S \subseteq V(G)$$, if $$i(G - S) \leq |S|$$, then a bipartite $$G = (X, Y)$$ has a perfect matching.

To do this, we prove the contrapositive: if $$G$$ has no perfect matching, then there exists a set $$S \subseteq V(G)$$ such that $$i(G-S) > |S|$$.

Indeed, it has to do with the "oddness" of each component. Suppose $$G$$ hs no perfect matching, there exists a set $$S$$ such that $$m := o(G - S) > |S|$$. Let the odd components of $$G - S$$ be $$C_1, \dots, C_m$$.

For each odd component, consider $$X_i = C_i \cap X$$ a nd $$Y_i = C_i \cap Y$$. Since $$C_i$$ is odd, either $$|X_i| > |Y_i|$$ or $$|Y_i| > |X_i|$$. Assume for now that $$X_i$$ is the smaller component (ie. $$|Y_i| > |X_i|$$). What happens when you remove $$X_i$$ from $$G-S$$? All the vertices in $$Y_i$$ becomes isolated vertices (this uses the fact that $$G$$ is bipartite), and the number of isolated vertices "produced" is $$\geq X_i + 1$$ (this uses $$|Y_i| > |X_i|$$ is a strict inequality).

If we go through each connected component, letting $$D_i$$ be the smaller component, (ie. $$D_i=X_i$$ if $$|Y_i| > |X_i|$$ and $$Y_i$$ if $$|X_i| > |Y_i|$$), we see that the set

$$T:= S \cup \bigcup_{i = 1}^m D_i$$ is exactly the set we want to use to obtain $$i(G - T) > |T|$$. This is because the removal of $$D_i$$ from $$G-S$$ produces at least $$D_i + 1$$ isolated vertices, so we have the inequality:

$$|T| = |S| + \sum_{i=1}^m |D_i| < m + \sum_{i=1}^m |D_i| = \sum_{i=1}^m |D_i| + 1 \leq i(G - T).$$

This gives us exactly what we want.