It is known that [Upfal]
Theorem. Given an undirected graph G with m edges, there is a partition of V into two disjoint sets A and B such that at least m/2 edges connect a vertex in A to a vertex in B. That is, there is a cut with value at least m/2.
The proof uses the probabilistic method and argues as follows: construct the partition $A|B$ by flipping independently one fair coin per vertex $v\in V(G)$, and assigning $v$ to $A$ if heads, to $B$ if tails. Denoting with $C(A,B)$ the (random) set of edges connecting a vertex in $A$ to a vertex in $B$, and with $|C(A,B)|$ its cardinality, we get that $$ \mathbb{E}(|C(A,B)|)=\frac{m}{2}, $$ since for every edge $e\in E(G)$, $e$ belongs to $C(A,B)$ with probability $1/2$. Hence, $$ \mathbb{P}(|C(A,B)|\geq m/2)>0 $$ and there must exist $A$ and $B$ such that $|C(A,B)|\geq m/2$.
I would like to prove the following
Corollary. Given an undirected graph $G$ with m edges, there is a cut with value strictly bigger than $m/2$.
I argued as follows. If there wasn't such a cut, the above random procedure would yield a cut with value strictly bigger than $m/2$ with probability zero. Hence, since $|C(A,B)|$ averages $m/2$, we would have $$ \mathbb{P}(|C(A,B)|)=\frac{m}{2}=1 $$ otherwise we would get to the following contradiction: $$ \frac{m}{2}=\mathbb{E}(|C(A,B)|)=\sum_{i=0}^{m}i\mathbb{P}(|C(A,B)|=i)=\sum_{i=0}^{m/2}i\mathbb{P}(|C(A,B)|=i)<\sum_{i=0}^{m/2}\frac{m}{2}\mathbb{P}(|C(A,B)|=i)= $$ $$ =\frac{m}{2}\sum_{i=0}^{|E|}\mathbb{P}(|C(A,B)|=i)=\frac{m}{2}. $$ Therefore, in particular, every cut would have cardinality equal to $|E|/2$. In particular, every vertex $v$ would satisfy $d(v)=|E|/2$, where $d(v)$ denotes the number of neighbours the vertex $v$ has in $G$, and we would have $$ |V|\frac{|E|}{2}=\sum_{i\in V}d(v)=2|E| $$ and |V| would be forced to equal $4$. But for any undirected graph $G$ on four vertices, the corollary is valid.
I would like to know if you see any problems here, and possibly if a quicker solution exists.