Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem
The problem is equivalent to the Maximum Independent Set problem on the &quot;bipartite complement graph&quot; (take the complement graph and delete edges with both endpoints on the same side of the bipartition). Such an MIS is the complement of a Minimum Vertex Cover, which can itself be deduced from a Maximum Matching.
You can probably take it from here (with maybe a bit of googling for how to find a Minimum Vertex Cover in a bipartite graph).