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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.