Prove that a graph on $n$ vertices which not contains $K_4$ as a subgraph has at most $\frac{n^2}{3}$ edges.

I tried prove that with induction. I assume for graph with $n-1$ vertices that has at most $\frac{(n-1)^2}{3}$ edges.

I take graph with $n$ vertices without $K_4$ as subgraph and I remove a vertex and his edges and if I try return him back with his edges it's not goes well.

any idea what is the problem with this way? I guess that I am missing something.


Let $G$ be such a (simple) graph on $n$ vertices. Verify small cases where $n\leq 3$. Now, suppose that $n>3$.

If $G$ contains no triangles, then it is well known that $G$ has at most $\dfrac{n^2}{4}<\dfrac{n^2}{3}$ edges (this is Mantel's Theorem). If $G$ contains a triangle, then let $H$ be the induced subgraph obtained from $G$ by removing a triangle. By induction, $H$ has at most $\dfrac{(n-3)^2}{3}$ vertices. Now, prove that the number of edges in $G$ that are not in $H$ is at most $3+2(n-3)$. Then, the number of edges of $G$ is at most $$\frac{(n-3)^2}{3}+3+2(n-3)=\frac{n^2}{3}\,.$$ More generally, see Turán's Theorem.

  • $\begingroup$ how should I know to do induction on $n-3$ vertices? because of the similarity to Mantel's Theorem? $\endgroup$ – UltimateMath Jul 21 '18 at 15:19
  • $\begingroup$ Well, it makes sense to remove three vertices because, if you have a triangle, you are going to have some obstructions when you add more edges until you get a maximal $K_4$-free graph. $\endgroup$ – Batominovski Jul 21 '18 at 15:22
  • $\begingroup$ This was a hard proof for me to follow: this is what I got: 1) Assume $G$ has $>\frac{n^2}{3}$ edges and no $K_4$. Then $G$ has a triangle $T$ by Mantel's Thm. 2) Remove $V(T)$ from $G$. Then the resulting graph $H$ has $n-3$ vertices and as $H$ has no $K_4$ either $H$ can have only $\frac{(n-3)^2}{3}$ edges by induction hypothesis. 3) $|E(G)|$ $\le 2(n-3)+3 +|E(H)|$ edges lest there is a $K_4$ w 3 of the vertices of the $K_4$ in $T$ as above. 4) Plugging in the upper bound of $\frac{(n-3)^2}{3}$ for $|E(H)|$ contradicts assumption of $|E(G)| \ge n^3/3$ gives desired upper bound on $|E(G)|$. $\endgroup$ – Mike Jul 21 '18 at 18:55
  • $\begingroup$ Nice proof! ..... $\endgroup$ – Mike Jul 21 '18 at 19:07

You could also use @Batominovski's line of reasoning and not even assume Mantel's Thm:

  1. Verify for $n=1,2,3$. Now assume for general $n$ that if $H$ is a graph on $n-3$ vertices and has no $K_4$, that $H$ has no more than $\frac{(n-3)^2}{3}$ edges.

  2. Now let $G$ be a graph with at least $\frac{n^3}{2}$ vertices and no $K_4$. Divide into 2 cases, Case 1 $G$ has a triangle $T$, and Case 2 $G$ does not have a triangle.

  3. For Case 1 [as the answer above] let $H$ be the graph on $n-3$ vertices formed from removing the vertices of $T$ from $G$. Then $H$ has no $K_4$ either and so by induction hypothesis $H$ has fewer than $\frac{(n-3)^2}{2}$ edges. But then $G$ must have fewer than $3+2(n-3)+|E(H)|$ $\le \frac{n^2}{3}$ edges too lest $G$ has a $K_4$ where 3 of the vertices are in $T$ and the fourth is a common neighbour in $G$ to the vertices of $T$.

  4. For Case 2 ($G$ is triangle-free too), let $u,u_1$ and $u_2$ be vertices in $G$ s.t. $u_1$ and $u_2$ are adjacent, and let $H$ be the graph formed by removing $u,u_1,u_2$ from $G$. As in Case 1 $H$ has no $K_4$ so it has no more than $\frac{(n-3)^2}{3}$ edges by the induction hypthesis. However, $G$ must have fewer than $2+2(n-3)+|E(H)|$ $\le \frac{n^2}{3}$ edges too lest $G$ has a triangle after all ($u_1,u_2$ and a common neighbor in $G$ in $V(H)$). So this is a contradiction too, and the result follows.


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.