I'm studying Engel book and the invariant principle, but the solution of problem E4 blocks me.
E4. 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 his own house.
Solution. 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 his own house. Now suppose A has at least two enemies in his own house. Then he has 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 intuitively understand why the function should work, but I can't prove it formally
I would start with a random distribution of members in the houses, and when we move one member to the other house, we potentially increase the cost of the second house. But how to show that it's guarantee that there is a minimum wich is also the solution to the problem?
Also, how can we formalize this solution mathematically? In particular this bit : 'Let H be the total sum of all the enemies each member has in his own house'