Putnam 1965 A4

A-4. At a party, assume that no boy dances with every girl but each girl dances with at least one boy. Prove that there are two couples $g b$ and $g^{\prime} b^{\prime}$ which dance whereas $b$ does not dance with $g^{\prime}$ nor does $g$ dance with $b^{\prime}$.