Parliament Pacification

In a parliament, each member has at most three enemies. (We assume that enmity is always mutual). Is the following statement TRUE (or) FALSE ?

  • One can always divide the parliament into two chambers in such a way that no parliamentarian has more than one enemy in his or her chamber.

If it is true, show how to divide. If it is false, show a counter example.

Source: from book "Algorithmic Puzzles"

Related Content