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...

  • 1
    $\begingroup$ 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$) ... $\endgroup$ – Hagen von Eitzen Apr 26 '15 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.