# Graph theory question involving probabilistic method.

I was trying to prove the following statement using probabilistic methods: Given that $G$ is a graph on $n\geq 10$ vertices, is a graph that has the property: If we draw a new edge, then the number of copies of $K_{10}$ increases. Prove that $|E|\geq 8n-36$.

I am interested in learning the subject but I am stuck in this problem. The idea that I have is that I should perhaps find some event $X$ such that $P(X)\geq (8n-36)/||E|$, but I dont know what should the event be.

Hints on how to start this problem would be greatly appreciated.

-

Here's one possible approach: consider the complement graph of $G$ and consider the pairs $(A_e,B_e)$, where $A_e$ contains the vertices of edge $e$ in $\bar{G}$ and $B_e$ contains all vertices that do not lie in a $K_{10}$ that $e$ completes. Try to find an upper-bound on the number of edges of $\bar{G}$ i.e. the number of such pairs.