Prove that every graph with m edges has a partition of its vertices into two sides with at least m/2 edges crossing between them, and explain how that existence argument becomes an algorithm.

Prove that every graph with m edges has a partition of its vertices into two sides with at least m/2 edges crossing between them, and explain how that existence argument becomes an algorithm.

Approach: Colour each vertex independently at random, compute the expected number of crossing edges by linearity, then argue that some outcome must meet the average and show how to find one deterministically.

Assign each vertex to one of the two sides independently with probability 1/2, so each edge crosses with probability 1/2 and the expected cut size is m/2, which forces some assignment to reach at least m/2. Linearity of expectation requires no independence between edges, which is why the probabilistic method works on an arbitrary graph with no structural assumption. The argument gives existence only, and derandomisation by the method of conditional expectations makes it constructive: process the vertices in any order and place each on the side that maximises the conditional expectation of the final cut, which holds the running expectation at or above its starting value and therefore ends at a cut of at least m/2. That greedy rule is exactly the local-search step that moves any vertex having more neighbours on its own side.

Follow-up: What lower bound does the same argument give for a partition into three parts?

Key concepts: linearity of expectation, probabilistic method, derandomisation, conditional expectations.