Problem regarding maximum number of independent sets and maximum degree

Question

Can someone please help me with this problem.
Show that a graph with n vertices with maximum degree d satisfies
$a(G)>=\frac {|V(G)|} {d+1}$, where a(G) is the maximum number of independent sets.

Answer 1

I think $a(g)$ should be the maximum size of an independent set. You can take a constructive approach. let $n=|V(G)|$

select a vertex and delte all of it's neighbors, there are now at least $n-(d+1)$ vertices. Select a vertex again and delete all of its neighbors(There are now $n-2(d+1)$ vertices. You can do this at least $\frac{n}{d+1}$ times. When you do this you shall have selected $\frac{n}{d+1}$ vertices and they will form an independent set since every time a vertex was selected we deleted all of its neighbors.

---

Note that if there is a vertex set $I$ of size $\frac{n}{d+1}$ it holds trivially that there are at least $\frac{n}{d+1}$ independent sets. Since any subset of $I$ will be independent and there are $2^\frac{n}{d+1}$ of those, which is more than $\frac{n}{d+1}$.