Basic Definitions: For a graph $G$ let us denote its vertex set by $V(G)$, its number of edges by $e(G)$, and for two disjoint subsets $V_1,V_2\subseteq V(G)$, let $e(V_1,V_2)$ denote the number of edges with one endvertex in $V_1$ and the other endvertex in $V_2$. Also for $v\in V(G)$, $G-v$ denote the subgraph obtained from $G$ by removing the vertex $v$ and all edges incident on $v$. Let $d(v)$ denote the degree of the vertex $v$, i.e. the number of edges incident on $v$.
Problem: Every graph $G$ has a bipartition $V(G)=U\sqcup W$ such that $e(U,W)\ge\frac12e(G)$.
My proof: I prove this via induction on the number of vertices, $n=|V(G)|$, of $G$. The base case is $n=2$, which is quite obvious, the bipartition is where $U$ contains one of the vertices and $V$ contains the other. So we assume the inductive hypothesis that the statement is true for all graphs with number of vertices $\le n$. Now take a graph $G$ with $n+1$ vertices. Choose any vertex $v\in V(G)$. Obviously $G-v$ is a graph with $n$ vertices and by our inductive hypothesis it has a bipartition $V(G-v)=U\sqcup W$, such that $e(U,W)\ge\frac12e(G-v)$. Now the degree of $v$ $d(v)=e(\{v\},U)+e(\{v\},W)$ and hence without loss of generality we assume $e(\{v\},U)\ge\frac12 d(v)$. Then let $W'=W\cup\{v\}$. Now $U\sqcup W'=v(G)$ is a bipartition of $G$ and \begin{multline} e(U,W')=e(U,W)+e(U,\{v\})\ge\frac12e(G-v)+\frac12d(v)= \frac12e(G) \end{multline}
I am looking for a much more intuitive or elegant proof, if there is any.
Proof 2. Choose a random bipartition by flipping an independent coin for every vertex to decide whether to put it in $U$ or $W$. Then each edge has a $\frac12$ probability to end up in $E(U,W)$, so the expected value of $e(U,W)$ is $\frac12 e(G)$. There must be at least one outcome which achieves at least the expected value.
Proof 3. Choose the bipartition that maximizes $e(U,W)$.
Then for each vertex $u \in U$, at least half of its neighbors are in $W$. Otherwise, we could increase $e(U,W)$ by moving $u$ to $W$: we'd lose all the edges from $u$ to $W$, but gain more edges from $u$ to $U$. By summing over all $u \in U$, we conclude that $e(U,W) \ge \sum_{u \in U} \frac12 \deg(u)$.
Similarly, for each vertex $w \in W$, at least half of its neighbors are in $U$. By summing over all $w \in U$, we conclude that $e(U,W) \ge \sum_{w \in W} \frac12 \deg(w)$.
Add these two inequalities, and we get that $2e(U,W) \ge \sum_{v \in V}\frac12 \deg(v) = e(G)$.