Number of $K_{10}$ always increases Let $G=(V,E)$ be a graph with $n\geq 10 $ vertices. Suppose that when we add any edge to $G$, the number of complete graphs $K_{10}$ in $G$ increases. Show that $|E|\geq 8n-36$.
[Source: The probabilistic method, Alon and Spencer 3rd ed., p.12, problem 5]
For the base case $n=10$, we know $G$ must have $44=8\cdot 10-36$ edges.
We know every vertex in $G$ must have degree $\geq 8$; otherwise adding an edge connecting that vertex cannot increase the number of $K_{10}$. This gives $|E|\geq 4n$.
 A: The solution to this problem uses a clever application of Theorem 1.3.3 (in "The Probabilistic Method, 3rd edition").  Since not everyone has access to the text, I will state the theorem (with necessary definitions) here first.
Definition: Let $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ be a family of pairs of subsets of an arbitrary base set.  $\mathcal{F}$ is a $(k,\ell)$-system if $|A_{i}|=k$ and $|B_{i}|=\ell$ for $1\leq i\leq h$, $A_{i}\cap B_{i}=\emptyset$ for all $1\leq i\leq h$, and $A_{i}\cap B_{j}\neq \emptyset$ for all $i\neq j$ with $1\leq i, j\leq h$.
Theorem (1.3.3) If $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ is a $(k,\ell)$-system, then $h\leq \binom{k+\ell}{k}$.
Now, the strategy to solve the original problem is to create a cleverly chosen $(k,\ell)$-system and apply the result.
Let $h$ be the number of edges not in $G$ and list the non-edges of $G$ as $\{e_1, e_2, ..., e_h\}$.  For each $e_{i}$ associate a set of 10 vertices that form a $K_{10}$ if $e_{i}$ were to be added to $G$.  The hypothesis guarantees that there is at least one such set of $10$ vertices; if there is more than one, pick one arbitrarily.  We will call this "potential" $K_{10}$, $K_{10}^{i}$ to denote that it is formed by adding edge $e_{i}$.  Each edge $e_{i}$ has two endpoints, call them $v_{i, 1}$ and $v_{i,2}$.  Form the set $A_{i}=\{v_{i, 1}, v_{i, 2}\}$.  Form the set $B_{i}=V(G)-V(K_{10}^{i})$, i.e. all the vertices in $G$ that are not in $K_{10}^{i}$, the chosen $K_{10}$ formed by adding edge $e_{i}$.  We want to verify that $\mathcal{F}=\{(A_{i}, B_{i})\}_{i=1}^{h}$ is a $(2, n-10)$-system.
Clearly, $|A_{i}|=2$ and $|B_{i}|=n-10$ for $1\leq i\leq h$.  Also clear is that $A_{i}\cap B_{i}=\emptyset$ for $1\leq i\leq h$ since the vertices in $A_{i}$ are contained in $K_{10}^{i}$.  For any $i\neq j$ note that at least one vertex of $e_{i}$ is not in $K_{10}^{j}$ otherwise, both $e_{i}$ and $e_{j}$ would need to be added to make $K_{10}^{j}$ a complete graph.  Thus, at least one vertex in $A_{i}\in B_{j}$ implying that $A_{i}\cap B_{j}\neq \emptyset$.  Thus, we do have a $(2, n-10)$-system.
By the theorem 1.3.3, $h\leq \binom{2+(n-10)}{2}=\binom{n-8}{2}$.  Since $h$ counts the number of non-edges of $G$, we can conclude that $G$ has at least $\binom{n}{2}-\binom{n-8}{2}$ edges.
And, (the easy part) 
\begin{align*}
\binom{n}{2}-\binom{n-8}{2} &= \frac{1}{2}\left(n(n-1) - (n-8)(n-9)\right) \\
&= \frac{1}{2}\left(n^2-n -(n^2 - 17n + 72)\right) \\
&= 8n-36.
\end{align*}
A: You already have most of the needed information for a proof. Using induction and very little additional work, you'll have your proof. 
We'll say graph $G$ has property $\mathcal{P}$ if adding any extra edge will increase its number of $K_{10}$s. Say, you have such a $G$ with $n > 10$ vertices. Now, what can you say (with respect to property $\mathcal{P}$) about the graph with $n-1$ vertices obtained by deleting an arbitrary vertex $v$ from $G$? You can use this answer, minimum degree information of $v$ and the principle of induction to finish the proof.
