4
$\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$

2 Answers 2

9
$\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$
3
$\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$

You must log in to answer this question.

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