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.
Problems that ask “is there an X with property Y” are very often in NP: If it is possible to show in polynomial time that an X has property Y, but also if for every X with property Y there is a proof that it has property Y that can be checked in polynomial time (this covers those cases where a proof that X has property Y is itself hard to find).
