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

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.

• how should I know to do induction on $n-3$ vertices? because of the similarity to Mantel's Theorem? – UltimateMath Jul 21 '18 at 15:19
• 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. – Batominovski Jul 21 '18 at 15:22
• 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)|$. – Mike Jul 21 '18 at 18:55
• Nice proof! ..... – 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.