A random cut crosses half the edges in expectation

Take one uniform two-point probability space per vertex and form their finite product; its outcomes are the maps $b:V\to \{0,1\}$ with the weights of [F2], so the bits $b_v$ are independent and each is $0$ or $1$ with probability $1\mathrm{/}2$. Interpret side $b_v$ as the side of vertex $v$; this is exactly the stated independent uniform placement.

For each edge $e=\{u,v\}$ define the indicator $X_e:={\mathbf{1}}_{b_u\mathrm{\ne }{b}_v}$ of the event that $e$ crosses the cut, and put $X:={\sum }_{e\in E}{X}_e$. At each outcome the sum counts precisely the crossing edges, so $X$ is the number of crossing edges.

Fix an edge $e=\{u,v\}$. The events $\{b_u=0\}$ and $\{b_v=1\}$ are coordinate events, so [F2] gives $\mathbb{P}[b_u=0,b_v=1]=\frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$; similarly $\mathbb{P}[b_u=1,b_v=0]=\frac{1}{4}$. The two cases are disjoint and exhaust $\{b_u\mathrm{\ne }{b}_v\}$, hence $\mathbb{P}[b_u\mathrm{\ne }{b}_v]=\frac{1}{4}+\frac{1}{4}=\frac{1}{2}$.

By [F3] and step 2.2, $\mathbb{E}[X_e]=\mathbb{P}[b_u\mathrm{\ne }{b}_v]=\frac{1}{2}$ for every edge $e$.

If $m=0$, then $X={\sum }_{e\in \mathrm{\varnothing }}{X}_e=0$ at every outcome by the empty-sum convention of [F3], so $\mathbb{E}[X]=0=m\mathrm{/}2$; also every placement crosses all zero edges, so ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}=0$, and both values are zero.

By linearity [F4] applied to the finite family $(X_e{)}_{e\in E}$, $\mathbb{E}[X]={\sum }_{e\in E}\mathbb{E}[X_e]=m\cdot \frac{1}{2}=m\mathrm{/}2$. The calculation uses only the individual probabilities of step 3.1; no independence between distinct edge indicators is assumed or needed.

Every placement yields a cut with at most $m$ crossing edges, since $G$ has $m$ edges in total; hence ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}\le m$, and step 4.1 gives $\mathbb{E}[X]=m\mathrm{/}2\ge {\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}\mathrm{/}2$.

Consequently the independent uniform placement produces a cut whose expected number of crossing edges is $m\mathrm{/}2$, at least half of ${\mathrm{OPT}}_{\mathrm{M}\mathrm{a}\mathrm{x}\mathrm{C}\mathrm{u}\mathrm{t}}$ in the value sense of [F5], with the zero-edge case covered by step 3.2.