1
$\begingroup$

I have to show that any graph with $n$ vertices and maximum degreee $d$ contains an independent set of size at least $\frac{n}{d+1}$. Why $d+1$? Can you please help me or give me a hint? Thanks a lot!

$\endgroup$
6
$\begingroup$

Take a vertex $v$ with $d$ neighbors. That's $d+1$ vertices.

Add $v$ to your independent set.

Remove $v$ and its neighbors from $G$ and repeat.

$\endgroup$
0
$\begingroup$

Another way to think about it, which also gives you a proper colouring, is the following: suppose the vertices are $1,\ldots,n$. Put vertex $1$ in a bin $B_1$. Suppose you have already split vertices $1,\ldots,j$ into some bins. Now, take vertex $j+1$, and put it in the first (occupied) bin in which it does not have a neighbour. If there isn't such, open a new bin and put it there.

Observe that this method will never open more than $d+1$ bins, as any vertex will find a bin among $d+1$ bins in which it does not have a vertex.

The generated bins are all independent sets, and thus make a proper colouring of the graph. The largest bin thus contains at least $n/(d+1)$ vertices.

This algorithm is sometimes called the greedy algorithm.

As for the question "why $d+1$", note that generally you cannot do better. The complete graph on $n$ vertices has $d=n-1$, but the largest independent set is of size $1=n/(d+1)$.

$\endgroup$

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.