If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge 1,$ then $a(G)\ge \frac{n}{k+1}$. Why?
(Here $a(G)$ is the independence number).
If $G$ is a graph with $n$ vertices and $\frac{nk}{2}$ edges, $k\ge 1,$ then $a(G)\ge \frac{n}{k+1}$. Why? (Here $a(G)$ is the independence number). 


This is also known as Turan's theorem. 


by turan theorem, that is very simple: a(G)=w(G')≥n^2/(n^22(n(n1)/2m))=n^2/(2m+n) 

