Entropy weight of a graph cover (${\sum }_{i}w(G_i)\ge n{\log }_2(n/\alpha )$)

If graphs $G_i$ cover the edges of an $n$-vertex graph with independence number at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an independent set, leaving conditional entropy at most ${\log }_2\alpha$. The mutual information carried by the colors is at most $n^{-1}{\sum }_{i}w(G_i)$, proving the bound.