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


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?


  • $\begingroup$ Apart from some minor mistakes in grammar/terminology, your proof is correct. $\endgroup$
    – M. Vinay
    Jul 1, 2016 at 14:13


You must log in to answer this question.

Browse other questions tagged .