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$.
On
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.
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*}