1
$\begingroup$

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...

$\endgroup$

2 Answers 2

1
$\begingroup$

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}$.

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .