MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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! – dvitek Sep 26 '10 at 19:30

This is also known as Turan's theorem.

share|cite|improve this answer
up vote 0 down vote accepted

by turan theorem, that is very simple:


share|cite|improve this answer
This seems to be exactly what Gjergji Zaimi has said in his answer – Yemon Choi Sep 28 '10 at 8:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.