# Independent Set Size Lower Bound for Graph

Suppose I have a graph $G$ with $n$ vertices, such that each vertex has degree at most $d$. How can I show that there is an independent set of size at least $\frac{n}{d+ 1}$?

My intuition is to use induction...

Every vertex that you choose to include in the independent set eliminates at most $d$ other vertices from being candidates of entering the independent set. So in total at most $d+1$ vertices are eliminated from consideration for each vertex which we put in the independent set. So there is an independent set of size at least $\frac n{d+1}$.
Enumerate vertices of $G$ in any order and then consecutively color them using at most $d+1$ colors such that a currently colored vertex is colored in a color different to all colors of all its already colored neighbors. Finally you obtain a coloring of vertices of $G$ such that any monochromatic set is independent. Since there are at most $d+1$ such sets, (at least) one of them has size at least $\frac n{d+1}$.