I initially encountered this problem in CLRS Intro to Algorithms, problem B-2.c:
[prove that] any group of people can be partitioned into two subgroups such that at least half the friends of each person belong to the subgroup of which that person is not a member.
I found some notes online by a Carnegie Mellon professor and former IMO gold medalist, that briefly discusses this problem (on page 3 of the notes):
Let G be a graph. It is possible to partition the vertices into two groups such that for each vertex, at least half of its neighbors ended up in the other group. Solution: Take a max-cut: the bipartition which maximizes the number of crossing edges.
That is all that is said. I also found a thread that discusses the same problem, and that too simply states that a max cut always solves the problem.
I found another thread that discusses a procedure for swapping vertices until the desired property is reached. The procedure is seen to be guaranteed to terminate since it always increases the number of crossing edges. (It is not certain and probably not true that such a procedure always reaches the max cut however, but I understand why it works.)
However, it is not immediately obvious to me why a max cut is guaranteed to solve the problem, and the way the result is stated in the first two links above seems to suggest that the result follows immediately simply from the fact that it is max cut. The initial theorem requires that every vertex must have at least half of its edges crossing the partition. How does this immediately follow from finding the partition the maximizes the total number of edges crossing?