# why is a max cut of an undirected graph guaranteed to result in each vertex having at least half its neighbors in other partition?

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?

• Regarding the relationship between the maximum cut and the swapping procedure: in general, it's typical of many graph theory proofs that for any solution along the lines of "Locally improve this structure until it cannot be improved further" there is an equivalent solution along the lines "Start with a maximal structure that cannot be locally improved". In this case, the structure is a vertex cut and "locally improve" means "move a vertex to the other side, increasing the number of cut edges". – Misha Lavrov Dec 1 '17 at 19:39