In a village there are an equal number of boys and girls of marriageable age. Each boy dates a certain number of girls and each girl dates a certain number of boys. Under what condition is it possible that every boy and girl gets married to one of their dates?(Polygamy and polyandry not allowed)
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
closed as off-topic by Zachary Selk, Davide Giraudo, sandwich, graydad, RecklessReckoner Nov 18 '15 at 3:24
This question appears to be off-topic. The users who voted to close gave this specific reason:
What you actually have is a bipartite graph and you are looking for a perfect matching. The theorem that provides a characterization for such conditions is Hall's marriage theorem: There exists a perfect matching for the graph if and only if for any set of boys $B$, $|B|\leq|N(B)|$ where $N(B)$ denotes the set of girls that date at least one of the boys from $B$.