= Solution
The <expectation> from part (f) is the average of $|S(\sigma)|$ over the finite collection of <permutations>. At least one value is as large as its average. By part (e), the corresponding $S(\sigma)$ is an <independent set>, so
$$
\boxed{\alpha(G)\geq\sum_{i=1}^n\frac1{d_i+1}.}
$$
Here $\alpha(G)$ is the <independence number>. Since its value is an <integer>, one can equivalently round the right side up with the <ceiling function>. This application of the <probabilistic method> is the <Caro-Wei bound>.
Back to article page
