We consider the problem of finding discrete clustering structures under the (sub-)Gaussian Mixture Models and the Stochastic Block Models. We establish a surprising property of the semidefinite programming (SDP) relaxations for these models: while the SDP solution is not integer-valued in general, its estimation error is upper-bounded by the error of the idealized integer program. As corollaries, we derive tight, exponentially-decaying error bounds on the clustering error of the SDP, and show that in certain regimes the SDP solution is in fact integral and exact.