Problem: Let $n$ be an even positive integer,
and let $G$ be an $n$-vertex (simple) graph
with exactly $\frac{n^2}{4}$ edges.
An unordered pair of distinct vertices $\{x,y\}$
is said to be \emph{amicable} if they have a common neighbor
(there is a vertex $z$ such that $xz$ and $yz$ are both edges).
Prove that $G$ has at least $2\binom{n/2}{2}$
pairs of vertices which are amicable.

Solution: First, we prove the following lemma.
(\url{https://en.wikipedia.org/wiki/Friendship_paradox}).
\begin{lemma*}
  [On average, your friends are more popular than you]
  For a vertex $v$, let $a(v)$ denote
  the average degree of the neighbors of $v$
  (setting $a(v) = 0$ if $\deg v = 0$).
  Then
  \[ \sum_v a(v) \ge \sum_v \deg v = 2 \# E. \]
\end{lemma*}
\begin{proof}
  Ignoring isolated vertices, we can write
  \begin{align*}
    \sum_v a(v)
    &= \sum_v \frac{\sum_{w \sim v} \deg w}{\deg v} \\
    &= \sum_{v} \sum_{w \sim v} \frac{\deg w}{\deg v} \\
    &= \sum_{\text{edges } vw} \left(
      \frac{\deg w}{\deg v} + \frac{\deg v}{\deg w} \right) \\
    &\overset{\text{AM-GM}}{\ge} \sum_{\text{edges } vw} 2
      = 2\#E = \sum_{v} \deg v
  \end{align*}
  as desired.
\end{proof}
\begin{corollary*}
  [On average, your most popular friend is more popular than you]
  For a vertex $v$, let $m(v)$ denote
  the maximum degree of the neighbors of $v$
  (setting $m(v) = 0$ if $\deg v = 0$).
  Then
  \[ \sum_v m(v) \ge \sum_v \deg v = 2 \# E. \]
\end{corollary*}

We can use this to count amicable pairs
by noting that any particular vertex $v$ is in
at least $m(v)-1$ amicable pairs.
So, the number of amicable pairs is at least
\[ \half \sum_v (m(v)-1) \ge \# E - \half \# V. \]

Note that up until now we haven't used any information about $G$.
But now if we plug in $\# E = n^2/4$, $\# V = n$,
then we get exactly the desired answer.
(Equality holds for $G = K_{n/2, n/2}$.)