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

graph theorymatching-theory

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).

Best Answer

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.

Related Question