Splitting a parliament into two houses

Idea. Use a monovariant: a nonnegative integer that strictly decreases at each step.

Process. Start with any split of the members into two houses. Let $E$ be the number of pairs of enemies belonging to the same house. If every member has at most one enemy in his own house, we are done. Otherwise, take a member $x$ with at least $2$ enemies in his own house.

Effect of the move. Since $x$ has at most $3$ enemies in total, he has at most $1$ enemy in the other house. Move $x$ to the other house.
- The pairs $\{x,y\}$ with $y$ an enemy in his former house are no longer in the same house: at least $2$ pairs are removed from the count.
- The pairs $\{x,y\}$ with $y$ an enemy in the other house now count: at most $1$ new pair.
- All other pairs are unaffected.

Hence $E$ decreases by at least $1$.

Termination. $E$ is a nonnegative integer, so the process cannot continue forever. When it stops, nobody has $2$ or more enemies in his own house.

Lesson. Monovariant: to prove a configuration with some property exists, start anywhere and improve a nonnegative integer quantity until it cannot be improved.