We show that the following two problems are polynomially equivalent: 1. Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not. 2. Given a (weighted) graphG, and a cutC ofG, decide whetherC is maximal or not, and in case it is not, find a better solutionC′. 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.