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

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

• well if your familar with the induction proof of halls theorem I think you can just adapt that unless your looking for something else – Hao S Aug 5 at 1:06

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.

• Do you see an easy to use your ideas to prove $d_H(b)\leq 1$ for all $b\in B$? (without showing first that $d_H(a)\leq 1$ for all $a\in A$, of course) – confusedStudent Aug 6 at 13:59
• Not really, you can go through steps 1-3 similarly, but I fail to see an immediate contradiction in that case. – Dániel G. Aug 6 at 14:01

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.