In an undirected graph $G = (V, E)$, a global maximum cut in $G$ is a pair $(S, V – S)$ with the largest possible number of edges with one endpoint in $S$ and another endpoint in $V – S$ (this quantity is called the size of the cut).
There is a well-known randomized approximation algorithm for finding a maximum cut that, on expectation, produces a cut of size $|E| / 2$ regardless of the graph. Consequently, this means that every graph must have a cut whose size is at least $|E| / 2$.
Although I completely understand why the above proof establishes why such a cut must exist, I don't have a good intuitive understanding of why this is the case. Is there a simple intuitive explanation for why every undirected graph must have a cut of size at least $|E| / 2$?
Thanks!
Best Answer
I think you can prove this using induction and the induction step will give some intuition for the situation. Let's leave out the base step (since it's trivial) and focus on the induction step, since we only care about intuition right now.
Take a graph $G = (V, E)$ and remove one arbitrary vertex $v$ and all it's adjacent edges $e_1, ..., e_k$. The resulting graph $G'$ has a cut of size $(|E| - k) / 2$ by the induction hypothesis. Now you can choose which side of the cut you put your left over vertex $v$ on. Choose the one that "adds more edges to the cut". Since you have $k$ edges adjacent to v, you add at least $k/2$ edges to the cut. So your graph $G$ has a cut of size at least $|E|/2$.
I think this step-by-step adding vertices in a way that makes the cut large gives a good intuition.