 Solution

As Boolean functions on edge indicators,Thus $g_m$ is the dual Boolean function of the clique function. Given a monotone circuit for $g_m$, swap every AND gate with an OR gate and swap the constants zero and one. De Morgan's laws show that the resulting circuit has the same size and computes ${\mathrm{CLIQUE}}_{n,m}$. The lower bound from part (v), with the same choice of $m$, therefore applies to $g_m$.