Optimization and optimality test for the Max-Cut Problem

The authors show that the following two problems are polynomially equivalent: (1) Given a (weighted) graph G, and a cut C of G, decide whether C is maximal or not. (2) Given a (weighted) graph G, and a cut C of G, decide whether C is maximal or not, and in case it is not, find a better solution C'. As a consequence, an optimality testing oracle may be used to design a polynomial time algorithm for approximately solving the (weighted) Max-Cut Problem. This in turn implies that recognizing optimal cuts in an unweighted graph is NP-hard.