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!
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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)$.
