The proof uses Hall's marriage theorem which is given this name because it is often explained as follows. Suppose there are "r" boys and "r" girls. The theorem states that if every subset of "k" boys (for each "k" such that 0 ≤ "k" ≤ "r") between them know "k" or more girls, then each boy can be paired off with a girl that he knows. It is obvious that this is a necessary condition for pairing to take place; what is surprising is that it is sufficient.