I have to show that any graph with $n$ vertices and maximum degreee $d$ contains an independent set of size at least $\frac{n}{d+1}$. Why $d+1$? Can you please help me or give me a hint? Thanks a lot!
[Math] size of an independent set of any graph with $n$ vertices and maximum degree $d$
graph theory
Best Answer
Take a vertex $v$ with $d$ neighbors. That's $d+1$ vertices.
Add $v$ to your independent set.
Remove $v$ and its neighbors from $G$ and repeat.