# In the marriage problem, if each girl knows at least $m$ boys, then there are at least $m!$ ways to arrange the marriages.

I'm finding problems concerning Hall's theorem very difficult even when they're not. (See here for example. I'm sure I wouldn't have come up with the solution in a million years even though it's probably one of the simplest solutions to any problem I've ever seen.) This one is probably easy too, but I have no idea how to approach it. Please, if you can, include in your answers some general tips because I'm starting to feel that I'm not able to learn to think about these things properly.

Suppose we have $n$ girls and $k$ boys satisfying Hall's condition for the existence of a marriage arrangment such that each girls is given a husband. Suppose additionally that each girl knows at least $m$ boys ($m\leq n$). I'm to show that there are at least $m!$ possible ways to arrange the marriages.

First, I think that it could be a good idea to change the assumption that the youth satisfy Hall's condition to the assumption that there exists at least one marriage arrangement. We can do this by Hall's theorem, and this is the idea I was missing in trying to solve the linked problem.

Second, I think it should be possible to solve this by induction on $m$. That's because there's a factorial involved. I thought at first that from the linked fact I could infer that any girl could marry anyone she knew, and then proceed by induction getting the result, but that's incorrect because of the following counterexample. Boys: a,b; girls: A,B; A knows a; B knows a and b. Now it is possible match them all, but B can't marry a even though she knows him.

Third, it wouldn't hurt to understand what the assumption that $m\leq n$ is for, which I don't.

This is really all I've got. I can't even solve the problem for $m=2$. Then I can assume we have each of the girls married to a boy and that each know some boy other then her husband. Then I need to show that I can divorce the couples and arrange them in a different way. But I don't know how.

-
@ErickWong I thought about this, but I decided it was false. Can't I take this situation? Boys: a,b,c; girls A,B,C, and A knows a, B knows b, and c knows B and C. Then there exists an arrangement, but c can't marry B even though she knows him –  Bartek Apr 7 '13 at 17:29
Ah, you're right. I overlooked the fact that choice only exists when there is a maximal matching not involving $c$. –  Erick Wong Apr 7 '13 at 17:31
In my previous comment it should have been "...C knows b and c. Then there exists an arrangement, but C can't marry b even though she knows him." –  Bartek Apr 7 '13 at 18:20

It is correct that induction on $m$ can be used to prove the result.

First let's introduce some notation. Let $G$ denote the bipartite graph with bipartition $A,B$, where $A$ is the set of girls and $B$ is the set of boys. We also know $|A|=k$, $|B|=n$ and $\deg(v)\geq m$ for all $v\in A$.

Base case ($m=1$): Since Hall's condition holds for $A$, we have (by Hall's theorem) that there exists a matching saturating all of $A$.

Induction hypothesis: Suppose any bipartite graph $G$ with bipartition $A,B$, satisfying Hall's condition for $A$, and such that $\deg(v)\geq m$ for all $v\in A$ admits $m!$ matchings saturating all of $A$.

Inductive step: Let $G$ be a bipartite graph as in the inductive hypothesis where $\deg(v)\geq m+1$ (instead of $\deg(v)\geq m$) for all $v\in A$. We will show that this graph admits $(m+1)!$ matchings saturating $A$.

Let $a\in A$ be such that every edge incident to it is in a matching saturating all of $A$ (see here for existence of such vertex). Let $b_1,b_2,\ldots,b_{m+1}$ be neighbours of $a$. Consider the graph $H_i=G-\{a,b_i\}$. The graph $H_i$ is bipartite, it satisfies Hall's condition for $A\setminus\{a\}$ (this follows since in $G$ there is a perfect matching containing $ab_i$) and $\deg(v)\geq m$ for all $v\in A\setminus\{a\}$. By induction hypothesis, there are $m!$ matchings in $H_i$ saturating $A\setminus\{a\}$. Each of these matchings in $H_i$ can be extended to matchings in $G$ containing $ab_i$ and saturating all of $A$. The result follows from counting the matchings, that is, there are $m!$ matchings in each $H_i$, $1\leq i\leq m+1$ for a total of $(m+1)!$ matchings.

Thanks to @darijgrinberg for his comment.

Edit: Vertex $a\in A$ cannot be chosen arbitrarily, it has to be chosen such that every edge incident to it belongs to a matching saturating all of $A$.

-
You can't pick a random $a$, you need an $a$ with the property that every edge from $a$ appears in some perfect matching of $G$. (The existence of such an $a$ is a known theorem, see e. g. artofproblemsolving.com/Forum/viewtopic.php?f=42&t=289103 .) –  darij grinberg Apr 8 '13 at 2:21
@Bartek Regarding the tips you asked about. For questions using induction it is usually good to ask yourself the following: "How does the inductive hypothesis help on proving the inductive step?" It might still not be obvious, and in that case it might provide insight to try to answer "How does the case $m=1$ help to solve the case $m=2$?". –  fidbc Apr 8 '13 at 2:37
@darijgrinberg is right. $a$ cannot be chosen arbitrarily. I'll uptade the answer. –  fidbc Apr 9 '13 at 15:09