The question is from the "Introduction to Algorithm" 3rd edition:
B-2 Friendly graphs: Reword the following statements as a theorem about undirected graphs, and then prove it. Assume that friendship is symmetric but not reflexive.
- 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.
Partition the graph into two arbitrary partitions $A$ and $B$ at first. Now, consider the set $S$ of edges between them, i.e. $S = \{(a,b) \in E \ | \ a \in A, \ b \in B\}$.
If some vertex $v \in A$ has more than half neighbours in $A$, then clearly shifting $v$ to $B$ increases the size of $S$. Similarly for any such vertex in $B$, shifting to $A$ increases the size of $S$.
This process must terminate in a finite number of steps since $S$ cannot increase forever.