Proof of Hall's marriage theorem via edge-minimal subgraph satifying the marriage condition

Question

I'm trying to reconstruct a proof of Hall's marriage theorem due to Kriesell.

Hall's marriage theorem A bipartite graph $G$ with bipartition $\{A,B\}$ contains a matching of $A$ iff $|S|\leq |N(S)|$, for all $S\subseteq A$.

The necessity of the marriage condition for the existence of the matching is trivial.

The proof strategy for the sufficiency of the marriage condition is to take $H\subseteq G$ to be edge-minimal s.t. it fulfills the marriage condition, show that $d_H(b)\leq 1$ for every $b\in B$, and from this derive that $G$ has a matching of $A$.

I've got the last step. (You just observe that if $d_H(b)\leq 1$ for every $b\in B$, different elements of $A$ have non-empty disjoint neighbourhoods.). However, the proof of $d_H(b)\leq 1$ for every $b\in B$ just eludes me. I know that it's probably very easy, but I've already been trying for hours and I'd appreciate your help. (Helpful hints are welcome and preferred over a solution).

Answer 1

I think I finally got it:

As above, let $G$ be a bipartite graph with bipartition $\{A,B\}$ which satisfies the marriage condition for side $A$, and let $H\subseteq G$ be edge-minimal, such that it satisfies the marriage condition. Towards a contradiction, assume that there exists a $b\in B$ with $d_H(b)\geq 2$. Let $a_0$ and $a_1$ be two distinct neighbours of $b$ in $H$.

Observe that by the choice of $H$, we can find two sets $A_0,A_1\subseteq A$ such that $a_i\in A_i$ and $|N_{H-a_ib}(A_i)|<|A_i|$, which implies $|N_H(A_i)|=|A_i|$ and $b\not\in N_H(A_i\backslash\{a_i\})$. Furthermore, we get $N_H(a_i)\backslash\{b\}\subseteq N_H(A_i\backslash\{a_i\})$ and, consequently, \begin{eqnarray*} |N_H(A_0\cup A_1)|-1 &=& |N_H(A_0\cup A_1\backslash\{a_0,a_1\})| = |N_H(A_0')\cup N_H(A_1')| \\ &=& |N_H(A_0')|+|N_H(A_1')|-|N_H(A_0')\cap N_H(A_1')|\\ &=& |N_H(A_0)|-1+|N_H(A_1)|-1-|N_H(A_0')\cap N_H(A_1')|\\ &=& |A_0|+|A_1|-|N_H(A_0')\cap N_H(A_1')|-2, \end{eqnarray*} with $A_i':=A_i\backslash\{a_i\}$. Now, since $A_0'\cap A_1'= A_0\cap A_1$ we can conclude $$|N_H(A_0')\cap N_H(A_1')|\geq |N_H(A_0'\cap A_1')|=|N_H(A_0\cap A_1)|$$ and thus, by the previous equality, \begin{eqnarray*} |N_H(A_0\cup A_1)|&=& |A_0|+|A_1|-|N_H(A_0')\cap N_H(A_1')|-1\\ &\leq& |A_0|+|A_1|-|N_H(A_0\cap A_1)|-1\\ &<& |A_0|+|A_1|-|N_H(A_0\cap A_1)| \end{eqnarray*} By the marriage condition we have $|N_H(A_0\cap A_1)|\geq |A_0\cap A_1|$, which finally gives us the contradiction to our choice of $H$: $$|N_H(A_0\cup A_1)|< |A_0|+|A_1|-|A_0\cap A_1| = |A_0\cup A_1|.$$

Please point out any mistakes you see.

Answer 2

I wouldn't say that this is "very easy", especially if you hadn't encountered some of these ideas before. Here is an outline of the proof in the form of hints.

1. A small, but important observation.

   It is, in fact, sufficient to show that $d_H(a) \leq 1$ for every $a \in A$. Why?

2. Technical steps.

   To show this, we argue by contradiction: suppose that there is some $a \in A$ with neighbours $b_1, b_2 \in B$. Let $e_i$ denote the edge $ab_i$ for $i = 1,2$. By the minimality of $H$, $H - e_i$ doesn't satisfy the marriage condition, so that there are sets $A_i \subseteq A$ such that $|N_{H-e_i}(A_i)| < |A_i|$. Examine $A_i$ closely; among other things, show that $A_i$ is tight in the sense that $|A_i| = |N_H(A_i)|$.

3. The key idea.

   Show that the intersection of tight sets is tight. To do this, you might want to find a relation between $|N(X)|, |N(Y)|, |N(X \cap Y)|$ and $ |N(X \cup Y)|$ that holds for any subsets of vertices $X,Y$ of any graph. In particular, $A_0 = A_1 \cap A_2$ is tight. Try to find a contradiction from this.

4. The final step.

   Show that $A_0 - a$ contradicts the marriage condition.

The "key idea" in this proof is an example of a general pattern/proof technique relating to so-called submodular functions. If you are interested in this technique, you might want to take a look at this paper.