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}

h_{i} \leq 1

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. Therefore

H (Y_{1}, \dots, Y_{ℓ} ∣ X) = \sum_{i} (1 - ∣ G_{i} ∣/ n) h_{i}, H (Y_{1}, \dots, Y_{ℓ}) \leq \sum_{i} h_{i} .

Any 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 ∣ Y_{1}, \dots, Y_{ℓ}) = 0

. The mutual information identity now gives

lo g_{2} n \leq \frac{1}{n} \sum_{i} ∣ G_{i} ∣ h_{i} \leq \frac{1}{n} \sum_{i} ∣ G_{i} ∣,

and hence

i \sum ∣ G_{i} ∣ \geq n lo g_{2} n

ii

Solution

For each

G_{i}

, choose a proper coloring minimizing its color information entropy

h_{i}

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

i \sum w (G_{i}) \geq n lo g_{2} n .

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