Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
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
3  
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
2  
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

2 Answers 2

This is also known as Turan's theorem.

share|improve this answer
up vote 0 down vote accepted

by turan theorem, that is very simple:

a(G)=w(G')≥n^2/(n^2-2(n(n-1)/2-m))=n^2/(2m+n)

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

Your Answer

 
discard

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.