# Graph Theory problem

This is a humorous graph theory problem, and I would love some pointers here. I'm finding the concept of matching a little challenging, so I'm not sure where to start.

Suppose we have $n$ pairs of girlfriends (with a total of $2n$ girls), another set of $2n$ boys. We want to romantically match each girl to a guy such that the girl can beat the guy at poker. Given any pair of girlfriends, say the $i$th pair, both girls in the pair can defeat at least $2i -1$ boys at poker. Also, if a girl cannot defeat a guy at poker, then her other girlfriend in the pair can defeat him. Can we find a matching so that each girl defeats her guy?

• Hall's Theorem should do the trick. – Nicolas Villanueva May 23 '11 at 17:54
• Hint for a more direct argument: match off the 1st pair and use induction. – Chris Eagle May 23 '11 at 18:07
• Thank you for the hints, I have seen Hall's theorem before and now matching is slowly clicking in my mind. @Chris, I like your direct approach, I just tried to reason through it in my head and it's illuminating. I think it shouldn't be difficult to produce the complete argument now. – John May 23 '11 at 18:14

You have a bipartite graph, girls on one side boys on the other. Put an edge between a girl and a boy if the girl can beat that boy at poker. Now, if you can show that for every set $S$ of girls, the set $\Gamma(S)$ of neighbors has cardinality $|\Gamma(S)|\geq |S|$, then a perfect matching exists by Hall's Marriage Theorem.