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/']
The question is ambiguous in two ways: we are not told whether being an enemy is a symmetric or asymmetric relation, nor whether the parliament has a finite or infinite number of members. I will show that the assertion is false for asymmetric relations, even in the finite case; in fact, I give an (asymmetric) example of $15$ people, each having only $2$ enemies, who can't be divided into two groups in which each member has at most one enemy. On the other hand, if the relation is symmetric, the assertion is true even in the infinite case.

**An asymmetric counterexample.** There are $15$ people, call them $x\_i,y\_i,y'\_i,z\_i,z'\_i\ (i=0,1,2).$ The enemies of $x\_i$ are $y\_i,y'\_i;$ the enemies of $y\_i,y'\_i$ are $z\_i,z'\_i;$ the enemies of $z\_i,z'\_i$ are $x\_i,x\_{i+1}$ (addition modulo $3$). Let each of the $15$ people be colored red or blue. Then at least two among $x\_0,x\_1,x\_2$ have the same color; without loss of generality, suppose that $x\_0,x\_1$ are red. If either $z\_0$ or $z'\_0$ is red, then we have a red person with two red enemies; so we may assume that $z\_0,z'\_0$ are blue. If either $y\_0$ or $y'\_0$ is blue, then we have a blue person with two blue enemies; so we may assume that $y\_0,y'\_0$ are red. But then $x\_0$ is a red person with two red enemies.

**The finite symmetric case.** (Already proved in the [answer](https://math.stackexchange.com/questions/2062522/each-person-has-at-most-3-enemies-in-a-group-show-that-we-can-separate-them-int/2062534#2062534) by @cats, repeated here for convenience.) If $G=(V,E)$ is a finite *undirected* graph with maximum degree at most $3,$ then the vertex set $V$ can be partitioned into two sets $V\_1,V\_2$ so that, for $i=1,2,$ each vertex in $V\_i$ has at most one neighbor (i.e. "enemy") in $V\_i.$ This can be done by choosing a partition which maximizes the number of edges with one endpoint in $\_1$ and the other in $V\_2.$ (This argument does not work if $V$ is infinite.)

**The infinite symmetric case.** If $G=(V,E)$ is any (not necessarily finite) undirected graph with maximum degree at most $3,$ then the vertex set $V$ can be partitioned into two sets $V\_1,V\_2$ so that, for $i=1,2,$ each vertex in $V\_i$ has at most one neighbor in $V\_i.$ This follows from the finite case by the usual sort of compactness argument, i.e., using the fact that the [Tychonoff product](https://en.wikipedia.org/wiki/Tychonoff%27s_theorem) of any family of finite spaces is compact.

**More generally,** let $k$ be a positive integer and let $d\_1,\dots,d\_k$ be nonnegative integers. If $G=(V,E)$ is any (not necessarily finite) undirected graph with maximum degree at most $d\_1+\cdots+d\_k+k-1$, then the vertex set $V$ can be partitioned into $k$ sets $V\_1,\dots,V\_k$ so that, for each $i=1,\dots,k$, each vertex in $V\_i$ has at most $d\_i$ neighbors in $V\_i$.

**Proof.** We may assume that $G$ is a finite graph and that $k=2$; the general case will then follow by induction on $k$ and a compactness argument. Let $d\_1,d\_2$ be nonnegative integers, and let $G=(V,E)$ be a finite graph with maximum degree at most $d\_1+d\_2+1$. Let $\{V\_1,V\_2\}$ be a partition of $V$ which minimizes the quantity $(d\_2+1)e\_1+(d\_1+1)e\_2$ where $e\_i$ is the number of edges joining two vertices in $V\_i$. Then each vertex in $V\_i$ has at most $d\_i$ neighbors in $V\_i$.
Let's separate it into two houses, House A and House B. If person $1$ has two or more enemies in House A, then we put him or her in House B. Then we take care of person $2$, etc. After just finitely many house changes (because we don't have infinitely many people), we can get each member to have at most one enemy in his or her house.