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