Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 / 4 / i / Solution

Choose $X$ uniformly among the $n$ vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write $h_i$ for that color information entropy, so $h_i\le 1$. The marginal distribution of $Y_i$ is precisely this color law, and the variables $Y_i$ are conditionally independent given $X$: present colors are deterministic and absent colors use independent dummy draws. ThereforeAny two distinct vertices are joined in some $G_i$ and have different forced colors there. They cannot both be compatible with the same observed color vector, so $H(X\mid Y_1,\dots ,Y_{\ell })=0$. The mutual information identity now givesand hence $\boxed{\sum _i|G_i|\ge n{\log }_{2}n}$.