# Imagine graph that has 10 vertices and 38 edges. Prove that there exist $K_4$ induced subgraph.

Imagine graph that has 10 vertices and 38 edges. Prove that there exist $$K_4$$ induced subgraph.

Such question already was asked here but I wanted to clarify some things.

One of people who answered claims that "There are only 7 edges missing from $$K_{10}$$" (what is obviously true). However is next statement is so: Each missing edge can prevent up to 28 different 4-vertex sets from inducing a $$K_4$$. If this is actually correct then we are done with proof. But I don't see why this is the case. Can you, please, explain this statement?

I was trying to prove it a bit differently: since we have 38 edges we have total sum of degrees equal to $$38 \cdot 2 = 76$$. Let us find pair of vertices with total degree equals 16 (such one definitely exists otherwise our total degree is not greater than 75 $$\Rightarrow$$ contradiction). There are basically two situations that we should consider. When one of vertices of this pair has degree 8 and another has degree 8 either and when one has degree 7 and another has degree 9. The second case is trivial. However, I am not managing to finish the first one.

Any help on that? (Please, do not use Turan's theorem if you want to show some alternative proof)

• What does "imagine" have to do with the question? Is this an imaginary graph? – Marc van Leeuwen Nov 27 '20 at 6:46
• You refer to some question that already was asked here. Please link to that question. – bof Nov 27 '20 at 7:48

Let $$u$$ and $$v$$ be any two vertices of $$K_{10}$$. There are $$\binom82=28$$ remaining pairs of vertices, so $$K_{10}$$ has $$28$$ distinct $$4$$-vertex sets containing the vertices $$u$$ and $$v$$. If you remove the edge $$\{u,v\}$$ from $$K_{10}$$, you’ve killed off these $$28$$ possible $$K_4$$ subgraphs.
• Looks good, thanks! Am I right now that together these 7 vertices missing prevent $28 \cdot 7$ $K_4$ subgraphs? But we have ${10 \choose 4}$ subsets of size 4 and it is more than $28 \cdot 7$. Probably $28 \cdot 7$ is just upper bound but not equality, right? – math-traveler Nov 27 '20 at 6:21
• @math-traveler: Yes, a given $K_4$ subgraph can be killed as many as $6$ times, once for each of its edges. $7\cdot 28$ simply gives us an upper bound on the number of $K_4$ subgraphs that are killed off. – Brian M. Scott Nov 27 '20 at 6:24
The cliques prevented by removing the edge $$ab$$ are those whose four vertices are $$a,b$$ and a choice of two from the remaining eight vertices, so they number $$\binom82=28$$.
Let $$f(n)$$ be the maximum possible number of edges in a $$K_4$$-free graph on $$n$$ vertices; we have to show that $$f(10)\lt38$$.
Let $$G$$ be a $$K_4$$-free graph with $$n$$ vertices ($$n\ge3$$) and $$f(n)$$ edges. Let $$p$$ be the number of pairs $$(e,v)$$ where $$v\in V(G)$$, $$e\in E(G)$$, and $$e$$ is not incident with $$v$$. Picking the edge first, we see that $$p=f(n)(n-2)$$. On the other hand, picking the vertex first, we see that $$p\le nf(n-1)$$. Thus, for $$n\ge3$$, we have $$f(n)\le\left\lfloor\frac n{n-2}f(n-1)\right\rfloor.$$ Starting with $$f(4)=5$$ we get successively $$f(5)\le8$$, $$f(6)\le12$$, $$f(7)\le16$$, $$f(8)\le21$$, $$f(9)\le27$$, and finally $$f(10)\le33$$.