It is difficult to appreciate that Bayes classifier yields smallest probability of error for a classification problem. As a matter of fact, as shown by Cover et al. the nearest neighbour classifier has twice the classification error at least asymptotically when compared to optimal Bayes classifier. It is not trivial to show that Bayes classifier has the lowest error rate. This rate is only achievable when joint distribution of data and associated class are known. Measure theoretic treatment and proof for this can be found here.

Further Reading on K-NN and its comparison with Bayes Classifier: Cover et al. Nearest Neighbor Pattern Classification