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 enemy in the group.

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.

Solution 1:

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.

Solution 2:

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 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 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$.

Solution 3:

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.