Let $m,n\in \mathbb{Z}$ such that $m<n$.Prove that if $G=(V,E)$ is a graph with $|V|=n$ without $m+1$ clique then $|E|\leq \frac{m-1}{m}n^2$.
Proof
Since the $G$ don't have $m+1$ clique then at most $G$ have a $m$ clique, it implies that $$|E|\leq \frac{m(m-1)}{2}\iff 2 |E| \leq m(m-1)$$ since $0<m<n$ then $(\frac{n}{m})^2\geq 0$ then if we multiply both sides by $(\frac{n}{m})^2$ we get $$ 2 |E| \left(\frac{n}{m}\right)^2\leq \frac{m-1}{m}n^2$$.
Now we claim $$|E|<2|E|\left(\frac{n}{m}\right)^2$$
Notice that $$|E|<2|E|\left(\frac{n}{m}\right)^2 \iff 2\left(\frac{n}{m}\right)^2> 1 \iff \left(\frac{n}{m}\right)^2>\frac{1}{2}$$
But since $0<m<n$ implies that $n=m+k$ for $k\geq 1$ and then $$\left(\frac{n}{m}\right)^2=\left(\frac{m+k}{m}\right)^2=\left(1+\frac{k}{m}\right)^2>1$$
Hence our claim is true and then $$|E|<2 |E|\left(\frac{n}{m}\right)^2\leq(\frac{m-1}{m}n^2$$ therefore $$|E|\leq \frac{m-1}{m}n^2$$ as well.
Is my proof right?
Hints.
Use induction on $n$. Let $G'$ be obtained from the graph $G$ by removing a vertex and $m<n-1$.
Since $$ |E(G)|\leq|E(G')|+n-1 \hbox{ and } |E(G')|\leq\frac{m-1}{m}(n-1)^2, $$ it follows that $$ |E(G)|\leq\frac{m-1}{m}(n-1)^2+n-1. $$ Now try to prove that $$ \frac{m-1}{m}(n-1)^2+n-1\leq\frac{m-1}{m}n^2 $$ provided that $m\geq2$. Investigate the cases $m=1$ and $m=n-1$ separately.