that a column is said to be good with respect to $S$, if the rows of $S$ have identical values on the column; a column is said to be bad with respect to $S$, otherwise. We shall argue that at least two of the three columns are bad with respect to $S$. Let us consider the three possible choices for two-column subsets out of the three columns.

-   Clearly, both the second and the third columns cannot be good with respect to $S$, since there are no other rows that contain $x$ in their second column and $y$ in their third column.

-   Next, we argue that both the first and the second column cannot be good with respect to $S$. Since, both $x$ and $y$ are perfect, their critical rows do not pay any extra cost. By Claim 2, the six (type \[type:AAA\]) rows of the form $\langle 0, x, x\rangle$ have gone to some cluster other than $S$. Similarly, the six (type \[type:AAA\]) rows of the form $\langle 0, y, y\rangle$ have also gone to some other cluster. These rows cannot be part of $S$. Now, since the graph is 3-regular, there are only two other edge rows 