Complexity of determining spanning bipartite graph
In answer to your comment:


  By maximum spanning bipartite graph I mean same vertex set as given graph and the maximum number of edges possible. Is the complexity $O(n^3)$ correct for this algorithm? If so it would solvable in P time.


No, that problem, also known as Bipartite Edge Deletion, or Edge Bipartization, is:


  Given a graph $G = (V, E)$ and an integer $k$, is it possible to delete at most $k$ edges $E'$ such that $G' = (V, E \setminus E')$ is bipartite,


which is NP-complete.

It happens to be "equivalent" to the "vertex deletion" version of the problem, which is also known as Odd Cycle Transversal.