Imagine that the graph is complete and each edge is either red or blue, and now we wish to count the number of ways to 2-color the graph such that the red and blue vertices are cliques if you look at the red and blue edges respectively.

Let ~r(v)~ be the number of red edges incident on ~v~. If ~v~ is red, then we can prove that all nodes ~w~ with ~r(w) > r(v)~ must also be red. This gives an ~\mathcal O(N)~ solution.

Note that this means the problem is solvable with only the degrees of the nodes - the actual graph is irrelevant otherwise.