Arthur Engel's book, "Problem Solving Strategies", includes the following problem (example 4, chapter 1, page 2):
In the Parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, so that each member has at most one enemy in their own house.
Engel has a very elegant solution to this problem (assuming the enmity relation is symmetric and anti-reflexive, and assuming the Parliament of Sikinia has a finite number of members):
Initially, we separate the members in any way into the two houses. Let $H$ be the total sum of all the enemies each member has in their own house. Now suppose $A$ has at least two enemies in their own house. Then they have at most one enemy in the other house. If $A$ switches houses, the number $H$ will decrease. This decrease cannot go on forever. At some time, $H$ reaches its absolute minimum. Then we have reached the required distribution.
I have a question about an alternative way of approaching this. The approach I'm considering is far less elegant (in fact it's quite ugly), but I am wondering if it works, too. I apologize if the explanation is hard to follow. I wasn't sure how to precisely explain what I was thinking.
My idea is as follows:
Suppose that the you divide the members of the Parliament of Sikinia into two arbitrary houses, let's say $A$ and $B$. I think I can show that, by a finite number of steps, you can successively reduce the number of people who have two enemies in the same house.
So suppose, for example, that $x$ is in $A$ and $x$ has at least two enemies in $A$. If you move $x$ to $B$, then the only way the total number of people who have at least two enemies in the same house won't be reduced is if $x$ has an enemy in $B$ whom I shall call $y$ such that, after $x$ is moved to $B$, $y$ will now have two enemies in $B$. If $y$ now gets moved to $A$, the only way the total number of people with two enemies in the same house won't get reduced is if there's another person $z$ in $A$ such that, after $y$ moves to $A$, $z$ will now have two enemies. Now the important point I think is that $z$ cannot be one of the enemies of $x$: $z$ isn't $y$ and if $x$ is one of the two enemies of $x$ other than $y$, than moving $z$ to $B$ will definitely reduce the number of people who have at least two enemies in the same house (if I move $z$ to $B$, the only enemy of $z$ in $B$ will be $x$). In other words, after a movement of a person from $A$ to $B$ and immediately subsequently a movement of a person from $B$ to $A$, all of the enemies of the person moved from $A$ to $B$ will be in $A$.
Working off of this, you keep on going like this (keep on moving people from $A$ and then from $B$), since $A$ is finite, the number of people in $A$ who are not enemies of people moved from earlier from $A$ to $B$ will eventually be zero. So eventually, by a finite number of steps, you can always reduce the number of people with two enemies in the house by one.
From here, my thought is that the reasoning above should work iteratively until there are no persons left who have two enemies in the same house.
Does this work?