1
$\begingroup$

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

$\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 Choi
    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$ Sep 26, 2010 at 6:28
  • 2
    $\begingroup$ Have you checked Bollobás' Extremal Graph Theory ? $\endgroup$ Sep 26, 2010 at 6:36
  • $\begingroup$ One should hope that in this case we have $k \ge 0$ too! $\endgroup$
    – dvitek
    Sep 26, 2010 at 19:30

2 Answers 2

7
$\begingroup$

This is also known as Turan's theorem.

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
1
  • 4
    $\begingroup$ This seems to be exactly what Gjergji Zaimi has said in his answer $\endgroup$
    – Yemon Choi
    Sep 28, 2010 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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