A cut containing at least half of the edges

Proof 1 (average). Put each vertex independently in $X$ or $Y$ with probability $\frac12$. A fixed edge $uv$ crosses iff $u,v$ land on different sides, which has probability $\frac12$. By linearity of expectation the expected number of crossing edges is $\frac m2$. A random variable cannot always be below its mean, so some choice of $X,Y$ gives at least $\frac m2$ crossing edges.

Proof 2 (local improvement). Start with any split. While some vertex $v$ has strictly more neighbours on its own side than on the other, move $v$ to the other side. This replaces the $a$ non-crossing edges at $v$ by crossing ones and the $b<a$ crossing edges by non-crossing ones, so the number of crossing edges increases by $a-b\ge1$. It cannot exceed $m$, so the process stops. At the end, each vertex $v$ has at least half of its edges crossing; summing over all vertices, every crossing edge is counted twice: $2\cdot(\text{crossing})\ge m$, so crossing $\ge\frac m2$.

Remark. For $K_n$ the best possible cut has $\lfloor n^2/4\rfloor$ edges, a proportion slightly above $\frac12$.

Lesson. When you need an object at least as good as average, compute the average (probabilistic method), or run a monovariant that improves a counter.