a graph $H_\phi$ that is $3$-colourable if and only if $\phi$ is satisfiable. We reduce [$3$-Satisfiability]{} to [Near-Bipartiteness]{} for graphs of diameter $3$ using the same construction, that is, we show that $H_\phi$ is near-bipartite if and only if $\phi$ is satisfiable. As such, our result is an observation about the proof of Mertzios and Spirakis, but, owing to the intricacy of $H_\phi$, this observation is non-trivial to verify. In Section \[s-diam3\] we therefore repeat the construction and describe our reduction in detail, though we rely on [@MS16] where possible in the proof.

Independent Feedback Vertex Set for Diameter $2$ {#s-poly}
================================================

In this section we show how to compute a minimum independent feedback vertex set of a graph of diameter $2$ in polynomial time. As mentioned, our proof relies on a known characterisation of near-bipartite graphs of diameter $2$ [@YY06]. In order to explain this characterisation, we first need to introduce some terminology.

Let $G=(V,E)$ be a graph and let $X\subseteq V$. Then the [*$2$-neighbour set*]{} of $X$, denoted by $A_X$, is the set that consists of all vertices in $V\setminus X$ that have at least two neighbours in $X$. A set $I\subseteq V$ is [*independent*]{} if no two 