Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.