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,\dots ,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,\dots ,n\}$, $$|D_i\cap D_j|=|D_i|+|D_j|-|D_i\cup D_j|\le 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\ge \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\ge \frac{1}{3}\left(\sum _{i=1}^n{d}_i^2-mn\right)\ge \frac{1}{3}\left(\frac{{\left({\sum }_{i=1}^n{d}_i\right)}^2}{n}-mn\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\ge \frac{1}{3}\left(\frac{(2m{)}^2}{n}-mn\right)=4m\frac{\left(m-\frac{n^2}{4}\right)}{3n}.$$