# Let graph $G = (V, E)$ $\Rightarrow$ $\alpha(G) \ge \frac{{|V|}^{2}}{2 \times (|E| + |V|)}$

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

Thanks anyway!

-

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

-
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