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

  • $\begingroup$ Could you add a page number for the source? $\endgroup$ – Barry Cipra Oct 20 '14 at 18:04
  • $\begingroup$ @BarryCipra Done. $\endgroup$ – simmons Oct 20 '14 at 18:57
  • 3
    $\begingroup$ $|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. $\endgroup$ – 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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Leen Droogendijk Oct 21 '14 at 12:52
  • $\begingroup$ @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$? $\endgroup$ – theconic Oct 21 '14 at 22:57
  • 5
    $\begingroup$ 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. $\endgroup$ – Leen Droogendijk Oct 22 '14 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.