# Proof verification: Mantel's theorem

if a graph $G=(V,E)$ on $n$ vertices contains no triangles than it contains at most $n^2/4$ edges.

Proof:

Let v$\in$V be a vertex of maximum degree k.

since G contains no triangles, there are no edges between each two of his $k$ neighbors. Thus, each neighbor has a maximum degree of n-k, by that we have that the sum of all $v$ neighbors degree is at most $k(n-k)$.

each of the other $n-k$ vertices in $G$ (which are not neighbors of v), including v itself, has maximum degree of k, by that, the sum of this vertices is at most $k(n-k)$.

So we conclude that $$2|E|=\sum\nolimits_{v \in V} deg(v) \leq 2k(n-k)$$ $$\Downarrow$$ $$|E|\leq k(n-k)$$ For each $k$, we know that $k(n-k) \leq n^2/4$

So, $$|E| \leq n^2/4$$

Will this proof compile? are there any missing details i didn't notice?

Thanks.

• Apart from some minor mistakes in grammar/terminology, your proof is correct. – M. Vinay Jul 1 '16 at 14:13