# How can i prove that MAX-CUT is in NP?

How can i show/explain/prove that Max-Cut is in NP? "For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem."

Thanks!

• The Wikipedia article you are citing tells you why it is easy to see that the decision version of the problem is in NP. Quote : "It is easy to see that the problem is in NP: a yes answer is easy to prove by presenting a large enough cut." – Tassle Aug 4 '19 at 20:51
• The NP version is, given a graph and an integer $k$, to determine whether the graph has a cut containing at least $k$ edges. – Yuval Filmus Aug 4 '19 at 21:12
• @Tassle - you are not helping. clearly i saw this cite in wikipedia. the question is why if i want to prove that max-cut is in NP is need to talk about the this decision problem. – user108220 Aug 5 '19 at 7:23

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