Bound on graph edges I need some help with the following problem.
Suppose I have a graph $G$ of $n$ elements such that each edge $e$ missing from it, is contained in a copy of $K_s$ (complete graph os $s$ vertices) in $G$ with $e$ added. I need to show that
$$ \left| E(G) \right| \geq {n \choose 2} - {n-s+2 \choose 2} $$
$\left| E(G) \right|$ is the number of edges of $G$
I appreciate any helps or thoughts on it, thanks.
 A: I solved the problem. It is by induction on the number of vertices.
The base case where $n=s$ is trivial. Now this means that $G$ has at least a pair of vertex $x$ and $y$ without and edge between them. By the property the graph has there is a $K_{s-2}$ in $G$ such that both $x$ and $y$ are connected to every vertex in $K_{s-2}$.
We construct a new graph $G'$ as follows, we remove $y$ from $G$, and for each vertex $z$ that was connected to $y$ that was not in that $K_{s-2}$ we add an edge between $z$ and $x$ (If it wasn't already connected). In this way $G'$ has one less vertex, and we removed at least $s-2$ edges. And beacause $G$ had no $K_s$ graph containing both $x$ and $y$ at the same time, and $x$ can now replace $y$ we didn't alter the property. So applying induction we have
$$ \begin{align}
|E(G)| &\geq |E(G')| + s - 2\\ 
&\geq {n-1 \choose 2} - {n-1-s+2 \choose 2} + s - 2\\
&= \left({n-1 \choose 2} + n \right) - \left({n-1-s+2 \choose 2} + n - s + 2 \right)\\
&= {n \choose 2} - {n-s+2 \choose 2}
\end{align}$$
