APMO, 1989

Call a triple $(a, b, c)$ good if and only if $(a, b), (a, c)$, and $(b, c)$ all belong to $S$. For $i$ in $\{1, 2, \ldots, n\}$, let $d_{i}$ be the number of pairs in $S$ that contain $i$, and let $D_{i}$ be the set of numbers paired with $i$ in $S$ (so $|D_{i}| = d_{i}$). Consider a pair $(i, j) \in S$. Our goal is to estimate the number of integers $k$ such that any permutation of $\{i, j, k\}$ is good, that is, $|D_{i} \cap D_{j}|$. Note that $i \notin D_{i}$ and $j \notin D_{j}$, so $i, j \notin D_{i} \cap D_{j}$; thus any $k \in D_{i} \cap D_{j}$ is different from both $i$ and $j$, and $\{i, j, k\}$ has three elements as required. Now, since $D_{i} \cup D_{j} \subseteq \{1, 2, \ldots, n\}$,
$$|D_{i} \cap D_{j}| = |D_{i}| + |D_{j}| - |D_{i} \cup D_{j}| \leq d_{i} + d_{j} - n.$$
Summing all the results, and having in mind that each good triple is counted three times (one for each two of the three numbers), the number of good triples $T$ is at least
$$T \geq \frac{1}{3} \sum_{(i, j) \in S} (d_{i} + d_{j} - n).$$
Each term $d_{i}$ appears each time $i$ is in a pair from $S$, that is, $d_{i}$ times; there are $m$ pairs in $S$, so $n$ is subtracted $m$ times. By the Cauchy-Schwarz inequality
$$T \geq \frac{1}{3} \left( \sum_{i=1}^{n} d_{i}^{2} - m n \right) \geq \frac{1}{3} \left( \frac{\left( \sum_{i=1}^{n} d_{i} \right)^{2}}{n} - m n \right).$$
Finally, the sum $\sum_{i=1}^{n} d_{i}$ is $2m$, since $d_{i}$ counts the number of pairs containing $i$, and each pair $(i, j)$ is counted twice: once in $d_{i}$ and once in $d_{j}$. Therefore
$$T \geq \frac{1}{3} \left( \frac{(2m)^{2}}{n} - m n \right) = 4m \frac{\left(m - \frac{n^{2}}{4}\right)}{3n}.$$