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.