$G$ contains two disjoint independent sets $A, B$ so that $|A| + |B| \geq 2\sum_{i=1}^n \frac{1}{d_{i}+1}$ where $d_{i}$ is degree of vertex $v_{i}$

184 Views Asked by At

Let $G$ be a graph on $n$ vertices with degrees $d_{1} \geq d_{2} \geq ...\geq d_{n} \geq 1$. Then, $G$ contains two disjoint independent sets $A, B \subset V, A \cap B = \emptyset$ such that $|A| + |B| \geq 2\sum_{i=1}^n \frac{1}{d_{i}+1}$.

I think that the approach to solving this problem is to use the probabilistic method, but I'm having a hard time setting it up since I don't really understand what the summation term means. Any help would be much appreciated.