# Existence of an independent set in a graph

I need to prove that any graph with $n$ vertices with maximal degree $t$ contains an independent set of size at least $\frac{n}{t + 1}$.

If $t \geq n-1$, this is obvious.

I tried induction on $n$ as follows (but failed):

If $v$ is the only vertex with maximal degree then we'll omit it and we are done but if not..?

For each vertex $v$ let $N[v]$ be the closed neighborhood of $v$, the set of all vertices adjacent or equal to $v$; by hypothesis, $|N[v]|\le t+1$. Let $S$ be a maximal independent set. Since $S$ is maximal, each vertex of $G$ is adjacent or equal to some vertex in $S$; in other words, $V(G)=\bigcup\{N[v]:v\in S\}$, whence $n=|V(G)|\le\Sigma_{v\in S}|N[v]|\le|S|(t+1)$, i.e., $|S|\ge\frac n{t+1}$. This shows that every maximal independent set contains at least $\frac n{t+1}$ vertices, which is stronger than saying that there exists an independent set with $\frac n{t+1}$ vertices.