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

1 Answer 1

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .