Proof of Hall’s marriage Theorem based on isolated vertex version

graph theorymatching-theory

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.

enter image description here
I have no idea about how to prove the sufficiency of the theorem.

Best Answer

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|$.
Related Question