Exercise 6.7

We first fix the number of nearest neighbours to $k$, and consider the neighbourhood of $N_S$ in $S$ and $N_D$ in $D$, both $N_S$ and $N_D$ have the same number of points, i.e. $k$.

We say $N_S$ and $N_D$ are not equal to each other, otherwise, $x_{\text{∗}}$ won’t be an inconsistent point. So there must be some point that is in $N_D$ but not in $N_S$.

Now we say that among these points that not in $S$, there must be a point $x^{\prime }$ such that $g_D(x^{\prime })=g_D(x_{\text{∗}})$.

If no such point exists, then all the points in $N_D$ but not in $N_S$ will have the class $g_S(x_{\text{∗}})$. Suppose the intersection of $N_D$ and $N_S$ has $m$ points, then $k-m$ points in $N_D$ will have class $g_S(x_{\text{∗}})$, when it combines with the intersection of $m$ points, we will definitely find that the class of $x_{\text{∗}}$ in $D$ to be $g_D(x_{\text{∗}})=g_S(x_{\text{∗}})$, because $N_S$ is composed of $k-m$ points plus the same $m$ points, but gives $x_{\text{∗}}$ a class of $g_S(x_{\text{∗}})$ without requiring the $k-m$ points to be all in class $g_S(x_{\text{∗}})$.

This is the contradiction, so we proved that the CNN heuristic will surely find a point $x^{\prime }$ that is not in $S$ and has class $g_D(x_{\text{∗}})$$$