1
$\begingroup$

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.

1 Answers 1

2

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.

Theorem 1.3.3 in the text by Alon and Spencer may be helpful.

  • 0
    Thank you! This helps a lot!2012-07-11