How can i prove that MAX-CUT is in NP?
The decision version of MAX-CUT is as follows:


  Given a graph $G$ and an integer $k$, is there a cut in $G$ containing at least $k$ edges?


This version is clearly in NP.