Recall that a max-cut partitions the vertices of a graph into two sets such that the number of edges crossing the cut is maximized. How can randomization help in finding such a partition efficiently?

Consider the simple randomized algorithm where each vertex is independently assigned to one of the two sets with equal probability. What is the expected size of the cut produced by this algorithm, and how does it relate to the optimal max-cut?

To derandomize this algorithm, use the method of conditional expectations. How can you systematically fix the assignments of vertices to sets while ensuring the expected cut size does not decrease, ultimately leading to a deterministic solution?