Para $n < s$ gráfico $G$ debe ser completa y la desigualdad, obviamente, se mantiene, por lo tanto más $n \ge s$. Vamos a probar la desigualdad por inducción en $n$ para cualquier constante $s$.
La base es $n = s$. En este caso, $|E(G)| \ge \binom n2 - \binom{n-n+2}{2} = \binom n2 - 1$ es verdad, porque si $G$ tiene falta de borde de $e$,$G + e \cong K_s$, por lo que todos los demás bordes están presentes, y en caso contrario, $G$ es completa.
Si $n > s$ vamos a considerar subgrafo $H \subset G$ $n - 1$ vértices y excluidos vértice $v \in V(G) \setminus V(H)$. Tenemos
$$\deg_G v \ge s-2,$$ because if $v$ is universal (adjacent to all other vertices), then $\deg_G v = n - 1 > s - 1 \ge s - 2$, and otherwise there is a missing edge $e = vu$ such that $G + e$ has clique $C$ of size $s$ containing vertex $v$, that implies $\deg_{G+e} v \ge s - 1$ and $\deg_G v \ge s - 2$. También por hipótesis de inducción
$$|E(H)| \ge \binom{n-1}2 - \binom{n-1-s+2}2.$$
Y, finalmente,
$$\begin{align}|E(G)| = |E(H)| + \deg_G v & \ge \binom{n-1}2 - \binom{n-1-s+2}2 + s-2 =\\
&=\binom{n-1}2 +\binom{n-1}1 - \binom{n-1-s+2}2-\binom{n-1-s+2}1 =\\
&= \binom n2 - \binom{n-s+2}2. \end{align}$$