# Friendly graph partitioning

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.
• Really? How interesting. – bof Oct 6 '14 at 2:54
• Is there a question here? It seems to be a statement. – Alan Oct 6 '14 at 3:52
• Why the downvote? It seems to be a legitimate question – iamvegan Oct 6 '14 at 4:28

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.