Karp hardness of searching for a matching cut
You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m&gt;|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.



Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.