[Math] Each person has at most 3 enemies in a group. Show that we can separate them into two groups where a person will have at most one enethe in the group.

algorithmscombinatoricsformal-proofsgraph theorypuzzle

The question that I saw is as follows:

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.

I built a graph where each person corresponds to a vertex and there is an edge between them if the two are enemies. Then I tried to color the vertices of the graph using two colors and remove edges that were between vertices of different colors. The goal is to arrive at a graph with max degree 1. I tried a couple of examples. It seems to workout fine, but I don't know how to prove it.

Best Answer

Split the house however you like. Let $E_i$ be the number of enemies person $i$ has in their group, and let $E = \sum E_i.$ For any person having more than $1$ enemy in their group, i.e. at least $2$, move them to the other group, where they will have at most $1$ enemy. This decreases $E.$ Since $E$ is always non-negative, this process must end eventually, at which point the desired configuration is reached.