4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.