Why is the maximum cut of an undirected graph at lest 1/2 the number of edges in the graph?

Question

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

A1-A2-...........-B1-B2-......-Bm

the max cut of the graph is just 1.

Am I misunderstanding the construct?

Answer 1

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.

Answer 2

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.