Let $G$ be a graph of order $n$. Show that $G$ must contain an independent set of $\left\lceil\sum_{v \in G} \frac{1}{d(v)+1}\right]$ vertices (where $\lceil x\rceil$ denotes the least integer $\left.\geqslant x\right)$.

[Hint: take a random ordering of the vertices of $G$, and consider the set of those vertices which are adjacent to no earlier vertex in the ordering.]

Fix an integer $m<n$ with $m$ dividing $n$, and suppose that $e(G)=m\left(\begin{array}{c}n / m \\ 2\end{array}\right)$.

(i) Deduce that $G$ must contain an independent set of $m$ vertices.

(ii) Must $G$ contain an independent set of $m+1$ vertices?