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?