Partitioning a graph with specific constraints We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills these constraints:


|V1| - |V2| = 0 or 1 (V1 and V2 have the same amount of nodes or V1 contains one node more that V2)
either


[case A] all nodes in V1 have edges to all nodes in V2
[case B] all nodes in V1 have no edges to any node in V2



We had a few ideas to find those partitions via divide-and-conquer involving the degrees of each node to differentiate between case A and B. If we find any node v with degree(v) &lt; |V2| then there is a partition with case B, otherwise if we find a node v with degree(v) > |V1| then there is a partition that fulfills case A.
However other than that we have been stuck and extendind or other ideas ended in a dead end.

How do we find those partitions? I'd like to not be given the answer but only a pointer to find a easy algorithm for the problem.
It suffices to be able to identify case&nbsp;B, since a graph satisfies case&nbsp;A if, and only if, its complement satisfies&nbsp;B.

A graph satisfies case&nbsp;B if, and only if, it is composed of components of size $n_1, \dots, n_\ell$ and there is some set $S\subset \{1, \dots, \ell\}$ such that $\sum_{i\in S} n_i = \sum_{j\notin S} n_j$.  (If $n_1 + \dots + n_\ell$ is odd, this is impossible, so include a fake component of size&nbsp;$1$.)

This is the set partition problem.  Bad news! It's NP-complete.  Good news!  It's not strongly NP-complete and we're encoding the numbers&nbsp;$n_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context.  By checking the algorithms carefully, you can probably avoid the "fake component" trick.