0
$\begingroup$

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.