# 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 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 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 at 7:23

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.

• What you are talking about the decision version? what is the formal way to do it? – user108220 Aug 5 at 7:21
• MAX-CUT can be considered both as a decision problem (as in my answer) and as an optimization problem (given a graph, find a cut maximizing the number of edges cut). The version you quote in your OP is unfamiliar to me. – Yuval Filmus Aug 5 at 7:22
• NP is a category of decision problems. Only decision problems can be in NP. – Yuval Filmus Aug 5 at 7:23
• The version im talking is this one (as you wrote): "given a graph, find a cut maximizing the number of edges cut" – user108220 Aug 5 at 7:25
• This is not a decision problem, so it cannot be in NP. Only decision problems can be in NP. A decision problem is one in which the answer is either Yes or No. – Yuval Filmus Aug 5 at 7:25