# Partition vertices of graph into two sets such that there are at least $k$ edges between sets [closed]

I have to show that for every integer $$k$$, the problem whether the vertices of input graph can be partitioned into two sets such that there are a least $$k$$ edges between the sets can be solved in polynomial time.

The only solution I can think of is that it is a maximum-cut problem a therefore it is NP-complete problem. So my question is am I on good track that it is a instance of maximum-cut problem or am I wrong?

• You should better ask such questions to your teacher. – Gamow Jan 30 at 20:34

Is $$k$$ considered a constant in this context? If so, the problem can be trivially solved in linear time. If $$|E| \geq 2k$$ then the answer is yes (there is always a cut of size at least $$|E|/2$$, since a random cut has size $$|E|/2$$ in expectation), and otherwise this problem can be solved in $$O(2^{4k})$$ rounds by enumerating over all possible cuts on vertices that have edges.

If $$k$$ can be arbitrarily dependent on $$n$$, then this is NP-complete, because max-cut can be reduced to it.