Problem:
In a group of people every person has less than enemies. Assume that is 's enemy iff is 's enemy. Show that we can divide the group into two parts, so that each person has at most one enemy in his part.
Problem:
In a group of people every person has less than enemies. Assume that is 's enemy iff is 's enemy. Show that we can divide the group into two parts, so that each person has at most one enemy in his part.
Solution:
We model the group as a graph where each person is a vertex and an edge connects two people if they are enemies. Each vertex has degree less than .
We need to partition the vertices into two sets so that each vertex has at most one neighbor (enemy) in its own set.
We proceed by induction on the number of people.
Base case: For or people, the statement is clear.
Inductive step: Suppose the statement is true for all groups with fewer than people. Consider a group with people.
Since every person has less than enemies, the graph has maximum degree at most .
Pick any person . Remove from the group. By the induction hypothesis, the remaining group can be partitioned into two sets and so that each person has at most one enemy in their own set.
Now, add back. has at most enemies, say , , (possibly fewer). These enemies are in and in some way.
If at most one of , , is in , put in ; then has at most one enemy in (his own set).
If at least two of , , are in , then at most one is in , so put in .
Thus, we can always place in a set so that he has at most one enemy in his own set.
This completes the induction.