= Solution
For each $G_i$, choose a proper coloring minimizing its color <information entropy> $h_i$, so its <coloring entropy weight> is $w(G_i)=|G_i|h_i$. A minimizing coloring exists: up to relabeling there are only finitely many partitions of its finite vertex set into color classes. Use independent dummy colors with the same marginal law as before. The marginal and conditional-entropy calculations in part (i) remain valid for any number of colors. Also any pair of vertices is joined in some covering graph and hence receives different forced colors there, so the full color vector still determines $X$. Thus
$$
\boxed{\sum_iw(G_i)\geq n\log_2n.}
$$
Back to article page
