say that a cycle of $G$ is a [*$2$-cycle*]{} if all its vertices have colour $2$. Our algorithm will consist of a number of branches depending on the way we will colour the vertices of $G$. Whenever we detect a $1$-edge or a $2$-cycle in a branch, we can discard the branch as we know that we are not going to generate a good $2$-colouring. Before we describe our algorithm, we first prove the following claim. Here, we say that an independent set $I$ is a [*twin-set*]{} if every vertex of $I$ has the same neighbourhood.

[[[*Claim .* ]{}]{}[*\[clm:1\]Let $I$ be a twin-set. In every optimal $2$-colouring, at least $|I|-1$ vertices of $I$ obtain the same colour.*]{}\
]{} We prove Claim \[clm:1\] as follows. If $|I|=1$, the claim is trivial. Suppose $|I|\geq 2$ and let $J$ be the neighbourhood of the vertices of $I$. Note that $J$ is non-empty since $|I|\geq 2$ and $G$ is connected. Let $c$ be an optimal $2$-colouring of $G$. If $c$ gives colour $1$ to a vertex of $J$, then every vertex of $I$ must receive colour $2$. Now suppose that $c$ gives colour $2$ to every vertex of $J$. If $|J|=1$, then $c$ colours 