Hall's Marriage Theorem

Hall’s Marriage Theorem provides a criterion to determine if it’s possible to match each person in one group to a unique partner in another group. Imagine two sets—say, men and women—and a list of who is willing to marry whom. The theorem states that a perfect matching exists (everyone paired off) if and only if, for any subset of men, the number of women they all know together is at least as large as the number of men in that subset. This ensures there are always enough potential partners to achieve a complete pairing.