 C \vert\geq (1-\delta)\vert C\vert$
    \item[$-$] $\vert N^{+}(v)\cap V\setminus C\vert \leq \delta \vert C\vert$.
\end{itemize}
If a vertex $v$ is not $\delta-$good with respect to $C$, then it is called $\delta-$bad
with respect to $C$. Finally, a set $C$ is $\delta-$clean if all $v\in C$ are $\delta-$good $C$.
\end{definition}
Intuitively, one should expect the number of mistakes of a clean clustering to be close to the number of mistakes of $\mathsf{O}\mathsf{P}\mathsf{T}$ since most of the edges are not in disagreement with a clean clustering. We formalize this in the following lemma.
\begin{lemma}\label{clean_lemma_BBC}
Given a clustering of $V$ in which all clusters are $\delta$-clean for
some $\delta\leq \frac{1}{4}$, then there exists a fractional packing $\{r_T\}_{T\in\mathcal{T}}$ such that the number of mistakes made by this clustering is at most $4\sum\limits_{T\in \mathcal{T}}r_T.$
\end{lemma}
\begin{proof}
Firstly, we give a procedure to associate a negative mistake $(u,v)$ with a bad triangle $T_{uvw}$ such that $u,v,w\in C_i$ for some $i\in [k].$ Then we show that the number of bad triangles chosen by this procedure sharing an edge is bounded above by some constant. This gives us a fractional packing of bad triangles with small total value.

Let $\mathcal{C}=\{C_1,\dots, C_k\}$ be a $\delta-$clean clustering. Let $(u,v)\in C_i\times C_i$ be a negative edge in disagreement that has not been considered so far. We want to choose a vertex $w\in C_i$ such that \textbf{(1)} both $(u,w)$ and $(v,w)$ are positive, and \textbf{(2)} it has not been picked by a negative edge in disagreement $(u,v')$ or $(u',v)$ in the previous steps. We associate $(u,v)$ with the bad triangle $T_{uvw}=(u,v,w).$ Observe that the second condition can be thought of as an attempt to enforce edge-disjointness on the triangles chosen by the procedure. We now show that such $w\in C_i$, in other words, such a bad triangle $T_{uvw}$ always exists.

Since $C_i$ is $\delta-$clean, we have $\vert N^{-}(u)\cap C_i\vert \leq \delta \vert C_i \vert$ and $\vert N^{-}(v)\cap C_i\vert \leq \delta \vert C_i \vert$. Thus there exist at least $(1-2\delta)\vert C_i \vert$ many vertices $w\in C_i$ such that both $(u,w),(v,w)\in E^{+}.$ For the same reasons, at most $(2\delta- 2)\vert C_i\vert$ many of these vertices might have been chosen by negative mistakes $(u,v')$ or $(u',v)$ before. Therefore, there are at least $(1-4\delta)\vert C_i \vert + 2$ many vertices available for $(u,v)$. This number is always positive since $\delta\leq \frac{1}{4}$.

Now we bound the number of bad triangles sharing a certain edge. Observe that a positive edge $(u,w)\in C_i\times C_i$ can appear in at most two bad triangles one due to a negative mistake $(u,v)\in C_i\times C_i$ and second possibly due to a negative mistake $(w,x)\in C_i\times C_i$. Furthermore, no edge having end points in different clusters can appear since the procedure chooses only in-cluster bad triangles. Thus, assigning $r_{uvw}=\frac{1}{2}$ for bad triangles $T_{uvw}$ chosen by the procedure and $r_{uvw}=0$ for bad triangles not chosen by the procedure we satisfy~(\ref{fractionalPacking}). Since for each negative mistake a bad triangle is picked, we have a fractional packing of bad triangles such that $\sum\limits r_{uvw}\geq \frac{1}{2}m^{-}_{\mathcal{C}}. $ 

Secondly, we give a similar procedure to associate a positive mistake $(u,v)$ with a bad triangle $T_{uvw}$ such that $u,v,w\in C_i\cup C_j$ for some $i,j\in [k].$ Using similar arguments we show that each edge can appear in at most constant number of bad triangles chosen by the procedure. This gives us a fractional packing of bad triangles with small total value which is different from the one constructed for negative mistakes.

Let $(u,v)\in C_i\times C_j$ for some $i\neq j$, be a positive edge in disagreement that has not been considered so far. Without loss of generality let $\vert C_i \vert\geq \vert C_j \vert$. We want to choose a vertex $w\in C_i$ such that \textbf{(1)} $(u,w)\in E^{+}$ but $(v,w)\in E^{-}$, and \textbf{(2)} it has not been picked by a positive mistake $(u,v')\in C_i\times C_k$ for some $i\neq k$ or by a positive mistake $(u',v)\in C_i\times C_j$ in the previous steps. We associate $(u,v)$ with the bad triangle $T_{uvw}=(u,v,w).$ Observe that the second condition enforces edge-disjointness on the triangles chosen by the procedure. We now show that such $w\in C_i$, in other words, such a bad triangle $T_{uvw}$ always exists.

Since $C_i$ is $\delta-$clean we have $\vert N^{+}(u)\cap C_i\vert \geq (1-\delta)\vert C_i\vert$. Similarly, since $C_j$ is $\delta-$clean we have $\vert N^{+}(v)\cap C_i\vert \leq \vert N^{+}(v)\cap \overline{C_j}\vert \leq \delta\vert C_j\vert\leq \delta \vert C_i \vert$. Thus, there exist at least $(1-2\delta)\vert C_i\vert$ many vertices $w\in C_i$ such that $(u,w)\in E^{+}$ and $(v,w)\in E^{-}.$ For the same reasons, at most $\delta (\vert C_i\vert+\vert C_j\vert)-2\leq 2\delta \vert C_i\vert-2$ many of these vertices might have been chosen by positive mistakes $(u,v')$ or $(u',v)$ before. Therefore, there are at least $(1-4\delta)\vert C_i \vert + 2$ many vertices available for $(u,v)$. This number is always positive since $\delta\leq \frac{1}{4}$.

Now we bound the number of bad triangles sharing a certain edge. Observe that a positive edge $(u,w)\in C_i\times C_i$ can appear in at most two bad triangles chosen by the procedure, one due to a positive mistake $(u,v)\in C_i\times C_j$ and second possibly due to a positive mistake $(w,x)\in C_i\times C_k$ for some $i\neq k$. Furthermore, a negative edge $(w,v)\in C_i\times C_j$ can appear in at most one bad triangle since the procedure picks vertices from $C_i$ and $v\in C_j$. Lastly, a negative edge in disagreement does not appear in any bad triangle. Thus, assigning $r_{uvw}=\frac{1}{2}$ for bad triangles $T_{uvw}$ chosen by the procedure and $r_{uvw}=0$ for bad triangles not chosen by the procedure we satisfy~(\ref{fractionalPacking}). This gives us a fractional packing of bad triangles. Since for each positive mistake a bad triangle is picked we have $\sum\limits r_{uvw}\geq \frac{1}{2}m^{+}_{\mathcal{C}}.$

Now depending on whether there are more negative mistakes or more positive mistakes, we can choose the corresponding fractional packing which gives the following
\begin{align*}
    m_{\mathcal{C}}=m_{\mathcal{C}}^-+m_{\mathcal{C}}^+\leq 2\max \{m_{\mathcal{C}}^-,m_{\mathcal{C}}^+\}\leq 4\sum\limits r_{uvw}.
\end{align*}
This finalizes the proof.
\end{proof}

This combined with Lemma~\ref{fractionalPacking_Lemma_BBC} give the following Corollary.

\begin{corollary}
The number of mistakes of a clustering in which all clusters are $\delta$-clean is at most $4m_{\mathsf