, 2023

Regard the problem as a graph $G = (V, E)$. For each point $v \in V$, let $d(v)$ denote the degree of that point. For each edge $e = uv \in E$, let $s(e) = d(u) + d(v)$, that is, the sum of the degrees of its two endpoints. We break this down into the following three steps:

1. Lemma 1: For each edge $e \in E$, there are at least $s(e) - 2n$ triangles having it as an edge.

Proof. Let the two endpoints of $e$ be $u$ and $v$. Then aside from $uv$, $A$ and $B$ together must connect $s(e)-2$ edges to the remaining $2n-2$ points, so by the inclusion-exclusion principle, at least $(s(e)-2) - (2n-2) = s(e) - 2n$ points have edges to both $A$ and $B$ simultaneously, that is, there are $s(e) - 2n$ triangles. □

2. Lemma 2: $S = \sum_{e \in E} s(e) \ge 2(n^2 + k)^2/n$.

Proof. Let us compute $S$ in two ways. Note that a point $v$ having degree $d(v)$ means it contributes a degree of $d(v)$ to $S$ on each of its $d(v)$ edges, so by the Cauchy-Schwarz inequality and the handshaking lemma,
$$\sum_{e \in E} s(e) = \sum_{v \in V} d(v)^2 \ge \frac{1}{2n} \left( \sum_{v \in V} d(v) \right)^2 = \frac{1}{2n} (2(n^2 + k))^2 = \frac{2(n^2 + k)^2}{n}.$$

3. Now, since each triangle has three edges, we have
$$\begin{aligned} 3 \times \text{number of triangles} &\ge \sum_{e \in E} (s(e) - 2n) \ge \frac{2(n^2 + k)^2}{n} - 2n(n^2 + k) \\ &= \frac{2k}{n}(n^2 + k) \ge \frac{2k}{n}(2n\sqrt{k}) = 4k^{3/2}. \end{aligned}$$