1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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|$.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .