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)
Best Answer
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.