Problem 1852

Let us define a bipartite graph $G$ as usual way. The boys and girls are vertices of the graph and pairs of friends are edges. It suffices to prove that the bipartite complement of this graph has a $(n - 2d)$ regular subgraph with $2n$ vertices.

Lemma. Let $G$ be a bipartite graph. $V(G) = A \cup B$ and all the vertices are between $A$ and $B$. Let $|A| = |B| = n$. If $k|X| \le e(X, Y) + k(n - |Y|)$ holds for any $X \subseteq A$ and for any $Y \subseteq B$, then there exists a $k$ regular subgraph of $G$, with vertices $V(G)$. ($e(X, Y)$ is the number of edges between $X$ and $Y$).

Proof of lemma. Let us consider the following directed graph $\tilde{G}$. $V(\tilde{G}) = V(G) \cup \{a, b\}$, $E(\tilde{G}) = \{(x, y) \mid x \in A, y \in B\} \cup \{(a, x) \mid x \in A\} \cup \{(y, b) \mid y \in B\}$. Now we define weight on the edges. All edges in $\{(x, y) \mid x \in A, y \in B\}$ have weight $1$, and all the remaining edges have weight $k$. Let us show that max-flow from $a$ to $b$ is $kn$. By MAX-FLOW, MIN-CUT theorem, it suffices to show that minimum cut is $kn$.
Assume that $X \subseteq A$ and $Y \subseteq B$ and $\{(a, x) \mid x \in X\} \cup \{(y, b) \mid y \in Y\}$ are all the edges that not affected by the cut. Then all the edges between $X$ and $Y$ must be affected. Thus, the weight of cut is at least $k|A - X| + k|B - Y| + e(X, Y) \ge k|A - X| + k|X| = k|A| = kn$. This completes proof of lemma.

Let $\tilde{G}$ be the bipartite complement of $G$. We need to show that $\tilde{G}$ has a $(n - 2d)$ regular subgraph with $2n$ vertices. By the lemma, it suffices to show that
$$(n - 2d)(n - |Y|) + e_{\tilde{G}}(X, Y) \ge (n - 2d)|X|, \forall X \subseteq A, \forall Y \subseteq B$$
or equivalently,
$$(n - 2d)(|X| + |Y| - n) \le e_{\tilde{G}}(X, Y), \forall X \subseteq A, \forall Y \subseteq B.$$
If $|Y| \le n - 2d$, then $|Y| + 2d - n \le 0$ and
$$(|X| + d - n)(|Y| + 2d - n) \ge (n + d - n)(|Y| + 2d - n) \ge d(2d - n).$$
$$(|X| + d - n)(|Y| + 2d - n) \ge (|X| + d - n)d \ge (2d - n)d.$$
If $n - 2d \le |Y|$ and $n - d \le X$ then from $d \le \frac{n}{2}$,
$$(|X| + d - n)(|Y| + 2d - n) \ge 0 \le d(2d - n).$$
If $|X| \le d$, then from $e(X, Y) \le |Y| \cdot |Y|$ and $|Y| \le |X| \le d \le \frac{n}{2}$,
$$(n - 2d)(|X| + |Y| - n) \le 0.$$
This completes the proof.