# 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$.

• Could you add a page number for the source? – Barry Cipra Oct 20 '14 at 18:04
• @BarryCipra Done. – simmons Oct 20 '14 at 18:57
• $|E|=8n-36$ is attained by the graph $G$ obtained by splitting one vertex of $K_9$ into $n-8$ independent vertices. I don't know why this would be the minimum. – bof Oct 20 '14 at 19:22

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*}

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.

• I fail to see how this works. If you take $n=3$ instead of $n=10$ and you take $G=C_5$, then $G$ has property $P$, but for any vertex $v$, $G-v$ does no longer have property $P$. – Leen Droogendijk Oct 21 '14 at 12:52
• @Leen Droogendijk: $C_5$, and any graph with $n < 10$ cannot have property $\mathcal{P}$, which is a property about having $K_{10}$. To have a $K_{10}$ in $G$ you need $n \geq 10$, which is why the base case for this induction is $n = 10$. Perhaps your confusion is from thinking $\mathcal{P}$ is the condition $|E| \geq 8n - 36$? – theconic Oct 21 '14 at 22:57
• No, "take $n=3$" is indeed confusing, but I meant, use 3 instead of 10. So P becomes "adding any extra edge will increase the number of $P_3$s". You cannot apply induction, at least I do not see how, and I do not see how the argument for $K_{10}$s is essentially different. – Leen Droogendijk Oct 22 '14 at 6:39