# Bounds on the independence number of a graph

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).

-
Since you're asking, who has set you the question, or where have you come across it? How much graph theory have you already studied or worked on? –  Yemon Choi Sep 26 '10 at 6:10
Dear Arash, I took the liberty of editing your post and changing the title (excuse me for this). You can edit and check how the TeX format works. Also note details as capital letters etc. Lastly, a precise title addressing to the question is superior to vague titles like "A maths question" &c. –  Pietro Majer Sep 26 '10 at 6:28
Have you checked Bollobás' Extremal Graph Theory ? –  Pietro Majer Sep 26 '10 at 6:36
One should hope that in this case we have $k \ge 0$ too! –  drvitek Sep 26 '10 at 19:30