2
$\begingroup$

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?

  • 0
    Thank you for the hints, I have seen Hall's theore$m$ 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.2011-05-23

1 Answers 1

3

Hint:
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.