In Upfal's Probability textbook he claims in Theorem 6.3

Given an undirected graph G with n vertices and 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.

I don't understand why this is necessary true. A quick counter example would be a graph like the following


the max cut of the graph is just 1.

Am I misunderstanding the construct?


The claim is that there exists a cut with the specified property. You have given an example of a cut which doesn't work, but there are also many examples which do work, for instance $$\eqalign{ A&=\{A_1,A_3,\ldots,A_{m-1},B_1,B_3,\ldots,B_{m-1}\}\cr B&=\{A_2,A_4,\ldots,A_m,B_2,B_4,\ldots,B_m\}\ .\cr}$$ Then in fact every edge of your graph connects a vertex in $A$ to a vertex in $B$. I'm assuming $m$ is even, but you can give a similar example if $m$ is odd.


Yes, you are. The two sets $A$ and $B$ don't have to be connected.
So for your line graph, number the vertices from left to right and take the odd-numbered and even-numbered vertices for $A$ and $B$ respectively.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.