# 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, 2014 at 2:54
• Is there a question here? It seems to be a statement.
– Alan
Oct 6, 2014 at 3:52
• Why the downvote? It seems to be a legitimate question Oct 6, 2014 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.