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