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)
- [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) < |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.