Derandomize MAX-CUT problem using $\log n$ bits

Question

Consider the MAX-CUT problem. We can flip $n$ coins to generate a random cut, and by linearity of expectation we get that with "good probability" our cut we'll be bigger then $\frac{n}{2}$.

Using pseudo random generators (XOR for example) we can generate $n$ pairwise independent bits from $\log n$ random bits. Using that approach, we can de-randomize the MAX-CUT problem with polynomial complexity.

With that algorithm, we are only checking $n$ possible cuts, where there are total of $2^n$. Is it promised that a "good" cut is within these $n$ cuts? Why?