good $2$-colouring for this branch.

The correctness of our algorithm follows from the fact that we distinguish all possible cases and find a best possible good $2$-colouring (if one exists) in each case. Note that it takes polynomial time to find the sets $S_1$, $S_2$, $T_1$ and $T_2$. Moreover, the number of branches is $O(n)$ and each branch can be processed in polynomial time, as we only need to search for a $1$-edge or $2$-cycle. Hence our algorithm runs in polynomial time.

\[l-2\] Let $G=(V,E)$ be a near-bipartite graph of diameter $2$ that contains no vertex $u$ such that $G-u$ is bipartite. Then it is possible to find a minimum independent feedback vertex of $G$ in polynomial time.

As $G$ is near-bipartite, it has an independent feedback vertex set. Let $A$ be a minimum independent feedback vertex set. We claim that $G$ contains a set of vertices $X$ of size $4\leq |X|\leq 5$ such that $A_X=A$. This would immediately give us a polynomial-time algorithm. Indeed, it would suffice to check, for every set $X$ of size $4\leq |X|\leq 5$, whether $(A_X,V\setminus A_X)$ is a near-bipartite decomposition and to return a set $A_X$ of minimum size that satisfies this condition. This 