 Solution

Use the same random variables for the edge cover of $G$. For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most $\alpha$ of them. By the maximum entropy on a finite alphabet, $H(X\mid Y_1,\dots ,Y_{\ell })\le {\log }_2\alpha$.

Consequently the mutual information is at least ${\log }_{2}n-{\log }_2\alpha$, while the marginal and conditional-entropy bounds from part (i) make it at most $n^{-1}{\sum }_{i}w(G_i)$. The entropy weight of a graph cover bound follows: