Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 17F / 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 }_{v}1/(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