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 Problem 7.26. Show that ≠ SAT ≤_P MAX-CUT. The variable gadget for variable x is a collection of 3c nodes labeled with x and another 3c nodes labeled with x̅, where c is the number of clauses. All nodes labeled x are connected with all nodes labeled x̅. The clause gadget is a triangle of three edges connecting three nodes labeled with the literals appearing in the clause. Do not use the same node in more than one clause gadget. Prove that this reduction works.