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

  • $\begingroup$ well if your familar with the induction proof of halls theorem I think you can just adapt that unless your looking for something else $\endgroup$ – 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.

  • $\begingroup$ 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) $\endgroup$ – confusedStudent Aug 6 at 13:59
  • $\begingroup$ Not really, you can go through steps 1-3 similarly, but I fail to see an immediate contradiction in that case. $\endgroup$ – 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.


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.