A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum number of edges possible) from given graph $G$:

Given a planar graph $G$. We need two disjoint sets $V_{1}$ and $V_{2}$. We define $V_{2} = V \setminus V_{1}$ where $V = V(G)$
In the following $H$ is the bipartite subgraph with $ V(H) = V_{1} \sqcup V_{2} $ and $E(H) = K_{V_1,V_2} \cap E(G) $ where $K_{V_1,V_2}$ is the complete bipartite graph with $V_1,V_2$

1. Start with first i vertices of V in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
2. In step i, let our current chosen vertex set be $V_{i1}$
3. If $\exists x \in V_{i1}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x)$ then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$\ $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex x which satisfies above property from $V_{i1}$ to $V_{i2}$.
4. Similarly do for $ V_{i2}$. $\exists x \in V_{i2}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x) $ Move vertex x to $V_{i1}$ .Go to step 2.
5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$.

We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure: Could somebody help me in analyzing this algorithm. Do I assume I know the degree of the vertices formed by the bipartite graph in the intermediate steps? If I assume so, then each induction iteration has 2n steps. And in the worst case could there be n! permutations of induction iteration( Any permutation of i vertices is possible for the first vertex set). Is the worst case upper bound O(n!*n)?

A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum possible number of edges) from given graph $G$:

Given a planar graph $G$, we need two disjoint sets $V_1$ and $V_2$. We define $V_2=V \setminus V_1$ where $V = V(G)$. In the following, $H$ is the bipartite subgraph with $V(H)=V_1 \sqcup V_2$ and $E(H) = K_{V_1,V_2} \cap E(G)$ where $K_{V_1,V_2}$ is the complete bipartite graph on $V_1$, $V_2$.

1. Start with first $i$ vertices of $V$ in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$

2. In iteration $i$, let our current chosen vertex set be $V_{i1}$

3. If $\exists x \in V_{i1}$ such that $d_{H}(x) \lt \frac12 d_{G}(x)$, then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$, $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex $x$ which satisfies above property from $V_{i1}$ to $V_{i2}$.

4. Similarly do for $ V_{i2}$. If $\exists x \in V_{i2}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x) $, move vertex $x$ to $V_{i1}$. Go to step 2.

5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$

6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$. We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure:

1. Could somebody help me analyze this algorithm?

2. Can I assume I know the degrees of the vertices in the bipartite graph $H$, in the intermediate steps?

2.1. If I can assume so, then each induction iteration has $2n$ steps. And, in the worst case, could there be $n!$ permutations of induction iteration  (Any permutation of $i$ vertices is possible for the first vertex set). Is the worst-case upperbound $O(n!\times n)$?

A procedure by induction to get maximum spanning bipartite graph from given graph $G$:

Given a planar graph $G$. We need two disjoint sets $V_{1}$ and $V_{2}$. We define $V_{2} = V \setminus V_{1}$ where $V = V(G)$
In the following $H$ is the bipartite subgraph with $ V(H) = V_{1} \sqcup V_{2} $ and $E(H) = K_{V_1,V_2} \cap E(G) $ where $K_{V_1,V_2}$ is the complete bipartite graph with $V_1,V_2$

1. Start with first i vertices of V in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
2. In step i, let our current chosen vertex set be $V_{i1}$
3. If $\exists x \in V_{i1}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x)$ then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$\ $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex x which satisfies above property from $V_{i1}$ to $V_{i2}$.
4. Similarly do for $ V_{i2}$. $\exists x \in V_{i2}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x) $ Move vertex x to $V_{i1}$ .Go to step 2.
5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$.

We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure: For each vertex in initial $V_{01}$ we do $(n-i)$ operations. Similarly for the other $(n-i)$ vertices in the other vertex set $V_{02}$ we do $i$ operations. We need to repeat this in the worst case i times. Hence upper bound is $O(n^3)$. So I am getting a polynomial time algorithm. What I am doing wrong. Is this not a NP problem. Could someone help me in analyzing this algorithm.

A procedure by induction to get maximum spanning bipartite graph (same vertex set as $G$ and the maximum number of edges possible) from given graph $G$:

Given a planar graph $G$. We need two disjoint sets $V_{1}$ and $V_{2}$. We define $V_{2} = V \setminus V_{1}$ where $V = V(G)$
In the following $H$ is the bipartite subgraph with $ V(H) = V_{1} \sqcup V_{2} $ and $E(H) = K_{V_1,V_2} \cap E(G) $ where $K_{V_1,V_2}$ is the complete bipartite graph with $V_1,V_2$

1. Start with first i vertices of V in vertex set $V_{01} \subseteq V$ and then $V_{02} = V \setminus V_{01}$
2. In step i, let our current chosen vertex set be $V_{i1}$
3. If $\exists x \in V_{i1}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x)$ then consider the bipartite spanning graph $H'$ with $V(H') = V_{i1}' \sqcup V_{i2}'$ where $V_{i1}' = V_{i1} \setminus x$, $V_{i2}'= V_{i2} \sqcup x$\ $E(H') = K_{V_{i1}',V_{i2}'} \cap E(G) $ This makes $\vert E(H') \geq E(H) \vert$. We are basically moving vertex x which satisfies above property from $V_{i1}$ to $V_{i2}$.
4. Similarly do for $ V_{i2}$. $\exists x \in V_{i2}$ such that $d_{H}(x) < \frac{1}{2} d_{G}(x) $ Move vertex x to $V_{i1}$ .Go to step 2.
5. Repeat until $(\forall x \in V(H))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$
6. After this $V_1 = V_{i1}$ and $V_2 = V_{i2}$.

We are using the property that a spanning bipartite subgraph $H$ from $G$ is maximal in terms of the total number of edges only when $H$ with $V(H) = V_{1} \sqcup V_{2}$ satisfies the property that $$(\forall x \in V(G))\, d_{H}(x) \geq \frac{1}{2} d_{G}(x)$$

Analysis of this procedure: Could somebody help me in analyzing this algorithm. Do I assume I know the degree of the vertices formed by the bipartite graph in the intermediate steps? If I assume so, then each induction iteration has 2n steps. And in the worst case could there be n! permutations of induction iteration( Any permutation of i vertices is possible for the first vertex set). Is the worst case upper bound O(n!*n)?