OBM 1996 Problem 5

There are $n$ boys $B_1, B_2, ... , B_n$ and $n$ girls $G_1, G_2, ... , G_n$ . Each boy ranks the girls in order of preference, and each girl ranks the boys in order of preference. Show that we can arrange the boys and girls into n pairs so that we cannot find a boy and a girl who prefer each other to their partners.

For example if $(B_1, G_3)$ and $(B_4, G_7)$ are two of the pairs, then it must not be the case that $B_4$ prefers $G_3$ to $G_7$ and $G_3$ prefers $B_4$ to $B_1$ .