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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.