A cut in an undirected graph is a separation of the vertices V into two disjoint subsets S and T. The size of a cut is the number of edges that have one endpoint in S and the other in T. Let MAX-CUT = {(G, k)| G has a cut of size k or more}. Show that MAX-CUT is NP-complete. You may assume the result of Prob- lem 7.26. (Hint: Show that #SAT
