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).
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ 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? $\endgroup$– Yemon ChoiCommented Sep 26, 2010 at 6:10
-
3$\begingroup$ 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. $\endgroup$– Pietro MajerCommented Sep 26, 2010 at 6:28
-
2$\begingroup$ Have you checked Bollobás' Extremal Graph Theory ? $\endgroup$– Pietro MajerCommented Sep 26, 2010 at 6:36
-
$\begingroup$ One should hope that in this case we have $k \ge 0$ too! $\endgroup$– dvitekCommented Sep 26, 2010 at 19:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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)
-
4$\begingroup$ This seems to be exactly what Gjergji Zaimi has said in his answer $\endgroup$ Commented Sep 28, 2010 at 8:36