Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 17F (Graph Theory)

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

Write $r=n/m$. The Cauchy-Schwarz inequality givesThe proved Caro-Wei bound therefore gives an independent set of at least $m$ vertices.

No. The disjoint union of $m$ copies of the complete graph $K_{n/m}$ has exactly the prescribed number of edges and has independence number $m$: an independent set can choose at most one vertex from each component, and choosing one from every component attains $m$.