# Reducing nearby enemies

[I got this puzzle from Jason Koenig.]
You are given an irreflexive symmetric (but not necessarily transitive)
"enemies" relation on a set of people. In other words, if person A is an
enemy of a person B, then B is also an enemy of A. How can you divide up
the people into two houses in such a way that every person has at least as many
enemies in the other house as in their own house?
[Hint: As Radu Grigore pointed out to me, solving the

Planar
configuration of straight connecting lines puzzle may provide a hint to
solving this puzzle.]

July 2011