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.
['https://math.stackexchange.com/questions/2062522', 'https://math.stackexchange.com', 'https://math.stackexchange.com/users/314798/']
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.
I will give a counter-example for the case where the enemy relationship is not assumed to be symmetric (but is assumed to be irreflexive). Imagine four kingdoms called North, South, East, and West. Each kingdom has many citizens and a king and a pretender to the throne (actually, the pretender to the throne might be the only citizen, awkward). The enemies of each citizen are the three foreign kings. The enemies of each king are the two next counterclockwise kings (North's enemy is West and South) as well as his pretender to the throne (each king has an enemy within his own kingdom).

Now let's first consider how to divide the kings. Clearly they can't go all in the same group. Also, if it is a 3-1 split, then two of the three may be happy because they hate the singleton, but the third of the three will hate the other two in the three, so a 3-1 split will not work. Now let's consider a 2-2 split, where the kingdoms pair off into two alliances. This may work for the kings, but we will need to make one observation: for either alliance, one of the king hates the other king (and possibly they both hate each other). For example, North is either paired with West or South, who North hates, or with East who hates North.

Now lets consider the placement of everyone else. Everyone besides the kings (including the pretenders) hate the three other kings. So each citizen has to be in his own kings alliance (because there are two enemy kings in the other alliance).

But now finally we get to a contradiction. In each alliance, there is a king who is allied with a king he hates. But then this king also hates the pretender in his own kingdom. Thus he has two people he hates.

User cardboard\_box found a simplification. In addition to the other citizens besides the pretenders being unnecessary, it can actually be the case that all the pretenders are one and the same, and they don't need to hate anybody. But since he is taking the role of all the pretenders, all the kings hate him. But now which alliance can he go in? As before, both alliances have a king who hates the other king in the alliance, and all kings hate the pretender, so he cannot go in either alliance, a contradiction. Thus only five people are necessary to provide a counterexample.