leino.science
© 2020-2024, K.R.M. Leino
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](/puzzles/#Planar-configuration-of-straight-connecting-lines) puzzle may provide a hint to solving this puzzle.