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