MathNet 2010 — Part 04 Question 74

Let $n$ and $d$ be positive integers satisfying $d \lt \frac{n}{2}$. There are $n$ boys and $n$ girls in a school. Each boy has at most $d$ girlfriends and each girl has at most $d$ boyfriends. Prove that one can introduce some of them to make each boy have exactly $2d$ girlfriends and each girl have exactly $2d$ boyfriends.

(proposed by B. Batbayasgalan, folklore)