Probabilistic Existence Proof for Maximum Graph Cut

Question

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}.$

Answer 1

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...