that have ‘$0$’ in their first column and ‘$x$’ in their second column; these correspond to the two other edges incident on $x$. There are three other rows (corresponding to the vertex $x$ and of type \[type:DDD\]) that have ‘$0$’ in their first column and ‘$x$’ in their second column. Thus, totally there are only 5 other rows that that have the above property. Since $|S|\geq 7$, it follows that both the first and the second column cannot be good with respect to $S$.

-   A similar argument shows that there are only 5 other rows that have ‘$0$’ in their first column and ‘$y$’ in their third column. This means that both the first column and the third column cannot be good in $S$.

We conclude at least two of the three columns are bad respect to $S$. Thus, the concerned edge row $\langle 0, x, y\rangle$ must pay a cost of at least 2. [$\Box$]{}

Let $V'$ be the set of all imperfect vertices. Let $E'$ be the set edges whose both endpoints are perfect. Each imperfect vertex (by definition) contributes at least 1 to the extra cost. By Claim 3, each edge in $E'$ pays an extra 