# Probabilistic Existence Proof for Maximum Graph Cut

Given a graph $G$ on $n$ vertices and $m$ edges a standard existence proof for a cut of size $\geq \frac{m}{2}$ is to randomly assign vertices to a cut $S\subseteq G(V)$ and then in expectation half of the edges cross the cut from $S$ to $\bar{S}.$ Again using a similar (or perhaps even the same) randomized method, how does one increase the existence bound to $\frac{mn}{(2n-1)}$? I've attempted using the same vertex assignment scheme but have not been able to improve upon $\frac{m}{2}.$

• Look for Noga Alon's Probabilistic Methods. This question is a theorem or an exercise in the first two chapters of the book, I believe. There is a hint there, I think, suggesting that one looks at subgraphs on $\lfloor n/2\rfloor$ vertices. – Batominovski Aug 18 '16 at 23:53

## 1 Answer

It's quite simple...

Partition verticies into two (almost) equal size parts uniformly randomly.

What is the expected value of cut size?

Every edge is in cut with probability $\frac{n}{(2n-1)}$ because after choosing the first vertex it remains $n$ choose for the second one among $2n-1$ remaining verticies.

Now use the same idea to solve it...