# Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $$G = (V, E)$$ and an integer $$k$$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $$k$$ or more edges have one end in each subset?

I'm a little confused on showing how the problem is NP, in terms of a certificate and certifier.

The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $$k$$ and answer accordingly YES or NO.
• @anon.g The certificate has say a number 0 or 1 for each vertex, so it has length linear in the number of vertices. This is given to the verifier, which runs in time linear in the number of edges: check each edge, increment count if necessary, and at the end do the comparison against $k$. – Juho Mar 13 at 19:40