# Partitioning a graph such that size of cut is maximum for number of vertices odd

Given a graph $G$ with $n$ vertices and $m$ edges, a cut $C$ of the graph are two disjoint subsets of the vertices $V_1$ and $V_2$ such that number of edges from $V_1$ to $V_2$ is maximum. This number is called the size of the cut $|C|$.

We can always find $C, |C| \geq m/2$ by a probabilistic argument. Send each vertex to $V_1$ with probability $1/2$ and $V_2$ otherwise. Then the expected number of edges between the two sets is $m/2$ and this ensures that there is some cut with atleast this size.

If $G$ has odd vertices, this bound can be improved to $m(n+1)/(2n+1)$ but I don't see how...

• On the other hand, $>m/2$ seems to be true as soon as $m>0$, for not all cuts can have $m/2$ then (for example if $V_1=\emptyset$) ... – Hagen von Eitzen Apr 26 '15 at 12:28