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?

  • 1
    $\begingroup$ Hall's Theorem should do the trick. $\endgroup$ – Nicolas Villanueva May 23 '11 at 17:54
  • $\begingroup$ Hint for a more direct argument: match off the 1st pair and use induction. $\endgroup$ – Chris Eagle May 23 '11 at 18:07
  • $\begingroup$ 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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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