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

Question

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.

Answer 1

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.

Answer 2

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.