= Solution
Take a uniformly random ordering of the vertices and select each vertex that precedes every neighbor. The selected set is <independent>: if two adjacent vertices were both selected, each would have to precede the other. Among the $d(v)+1$ vertices consisting of $v$ and its neighbors, each is equally likely to come first, so the selection probability is $1/(d(v)+1)$. Linearity of <expectation> gives expected size $\sum_v1/(d(v)+1)$. At least one ordering attains at least this average; its <integer> size is therefore at least the ceiling. This proves the <Caro-Wei bound>
$$
\boxed{\alpha(G)\ge\left\lceil\sum_v\frac1{d(v)+1}\right\rceil.}
$$
Back to article page
