Prove that every graph $G$ with m edges

Question

Prove that every graph $G$ with m edges admits a bipartition $V(G) = V1 ∪V2$ such that the number of edges of $G$ crossing between $V1$ and $V2$ is at least $m/2$

I think to prove that in contradiction but I'm not sure how ...

Answer 1

Start with $V_1=V(G),V_2=\emptyset$. Proceed as follows: for every vertex in $V_1$, if moving it to $V_2$ increases the number of edges between $V_1$ and $V_2$, do that. Otherwise leave it alone. After going over all vertices, this should produce a partition as desired. I leave the proof itself up to you.

Answer 2

Start with an arbitrary partition $V_1,V_2$. Now if we have less than $m/2$ edges between $V_1$ and $V_2$ then there exists a vertex (suppose $x\in{}V_1$) such that $x$ has more neighbors in the other class ( $V_2$ ) (otherwise for each vertex $v$ we would have at least $deg(v)/2$ edges between $V_1$ and $V_2$ and thus more than $\frac{1}{4}\sum_{v\in{}|V|}deg(v)= m/2$ edges). Then set ${V_1}'=V_1/\{x\}$ and ${V_2}'=V_2\cup\{x\}$. Each time you do this you increase the edges between $V_1$ and $V_2$ by at least $1$ and thus the proccess terminates after at most $m/2$ steps.

Answer 3

The other answers describe an algorithmic approach; here I describe the standard probabilistic approach.

Choose the partition randomly as follows: with probability $\frac{1}{2}$, we independently choose each vertex to either be in $V_1$ or $V_2 = V \setminus V_1$. The probability a given edge $e$ crosses between $V_1$ and $V_2$ is $\frac{1}{2}$ (this is calculated by noting that the endpoints of $e$ need to be in different parts; if one endpoint is in one part, the other endpoint is in the other part with probability $\frac{1}{2}$). Now we calculated the expected number of edges crossing between $V_1$ and $V_2$:

$$ \mathbb{E}[e(V_1, V_2)] = \sum_{e\in E(G)} \mathbb{E}[1_e] = \sum_{e\in E(G)} P(e \in [V_1, V_2]) = \sum_{e\in E(G)} \frac{1}{2} = \frac{m}{2} $$

where $1_e$ is the indicator random variable for an edge $e$ crossing between $V_1$ and $V_2$ ($1$ if $e$ does cross and $0$ if it does not). Since the expected number of edges in the bipartition is $\frac{m}{2}$, there exists some bipartition with at least this number of edges.