\[clm:2\]. Again, in this case we discard the branch if a $1$-edge or $2$-cycle is found; otherwise we remember the corresponding $1$-set if it is the best set found so far. In every other case, we must have coloured every vertex of non-empty set $S_2\cup T_2$ with colour $2$. Without loss of generality, assume that there is a vertex $s \in S_2$ that is coloured $2$. Then at most one vertex of $T_1'$ may have colour $2$, as otherwise we obtain a $2$-cycle by involving the vertices $s$ and $u$. We branch by guessing this vertex and then colouring it either $1$ or $2$, while assigning colour $1$ to all other vertices of $T_1'$. Then the only vertices with no colour yet are in $S_1'$, but their colour is determined by the colours of the vertices in $T_1'$ due to Claim \[clm:2\].

We are left to deal with the case where $S_2\cup T_2=\emptyset$. Claim \[clm:2\] tells us that we must either give every vertex of $D_i^1$ colour $1$ and every vertex of $D_i^2$ colour $2$, or vice versa. For $i \in \{1,\ldots,r\}$ we give colour $1$ to every vertex of every $D_i^1$; as $|V(D_i^1)|\leq |V(D_i^2)|$, this is the best possible 