1
$\begingroup$

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)

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

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – math-traveler Nov 27 '20 at 6:21
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Nov 27 '20 at 6:24
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.