Given an undirected graph $G=(V,E)$, the max-cut problem asks for the partition $S_1,S_2\subset V$ , s.t., the number of edges going from $S_1$ to $S_2$ are maximized. 

![Maximum cut][1]

Is it possible to maximize the sum of all edges between $S_1$ and $S_2$ at the same time we minimize the sum of internal edges in $S_1$ partition?  


  [1]: https://i.sstatic.net/Nxhsp.png