Given an undirected graph G = (V, E), the max-cut problem asks for the partition S1, S2 ⊆ V , s.t., the number of edges going from S1 to S2 are maximized.
Is it possible to maximize the sum of all edges between S1 and S2 at the same time we minimize the sum of internal edges in S1 partition?