Let rho = E[Pi_{(i,j) \in S} f(x^{(i)}x^{(j)}) f(x^{(i)})f(x^{(j)})].
Without loss of generality, assume (1,2) is an edge in S.
Show that there are  settings for x^{(3)}...x^{(k)}
so that   E_{x^{(1)},x^{(2)}}[Pi_{(i,j) \in S} f(x^{(i)}x^{(j)}) f(x^{(i)})f(x^{(j)})] is at least rho.
Now show that an argument similar to that
of problem 1 (linear consistency testing) gives the bound.