Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$, where $\alpha(G)$ is the vertex independence number of $G$.

Give some clue please!

Thanks anyway!

share|cite|improve this question
up vote 3 down vote accepted

Since this is tagged homework, here's a sketch of a proof.

We can use the greedy algorithm to get a lower bound on $\alpha(G)$. At each step we choose the vertex of least degree, and place it in our independent set. We then delete it, along with its neighbours, and repeat until we run out of vertices. If the greedy algorithm runs for $t$ steps, then $\alpha(G) \geq t$. A rather slick proof that $t \geq |V(G)|/(\overline{d}+1)$, where $\overline{d}=\frac{2|E(G)|}{|V(G)|}$ is the average degree, was given in:

Halldorsson and Radhakrishnan, Greed is Good: Approximating Independent Sets in Sparse and Bounded-Degree Graphs (pdf), Algorithmica (1997) 18:145-163.

This inequality can be re-arranged to show \[\alpha(G) \geq t \geq \frac{|V(G)|^2}{2(|E(G)|+|V(G)|)}\] whenever $|E(G)| \geq |V(G)|-1$.

share|cite|improve this answer
Ok, I will check this sketch. But Is it able (is it real..) to prove this without Approximating value..? Because at this moment for proving we don't use articles of this type. – brainail Oct 8 '12 at 8:27
I'm not sure what you mean, there's no approximations here. Although, I must admit, this answer seems quite difficult for a "homework" question -- possibly there's a more simple proof (it might be easier to spot if you list what topics you've been studying recently). – Douglas S. Stones Oct 8 '12 at 8:45
I think it's too much to list in detail what we studied .. I can say just: Connectedness, independent set of bipartite graphs, matroids a little (I think this can be attributed to the greedy algorithm), the properties of the graph, the graphs of various types .. – brainail Oct 8 '12 at 22:30
Sorry, it's not ringing any bells for me. Perhaps someone else is able to offer a more efficient idea. – Douglas S. Stones Oct 9 '12 at 1:54
I will try to understand your idea. – brainail Oct 9 '12 at 5:44

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.