Split hateful people into groups that can exist in harmony (color a graph) There are 51 people. Each person hates exactly 3 other people (who may or may not reciprocate). We need to split them into $n$ groups so that all groups exist in harmony.

What is min $n$?

Edit
We need to find $n$ such that, whatever the graph, $n$ groups will be enough to accomplish our goal. I see it was not clear initially.
Attempt
Tried to prove $n=5$ by considering 1 parent and 3 children of a node. Hence 1(parent)+3(children)+1(self) = 5. But this solution fails to consider other parents
 A: Phrase this as a coloring problem: we are trying to find a proper coloring of a graph whose vertices are the people, with an edge between two people whenever one of them hates the other.
This graph is $6$-degenerate: in any subgraph, there is a vertex of degree at most $6$. We can see this because the average degree in any subgraph is at most $6$ (if there are $n$ vertices in the subgraph, then there are at most $3n$ edges) and there must always be a vertex whose degree is at most the average degree.
A $k$-degenerate graph can be colored with $k+1$ colors, so this $6$-degenerate graph can be colored with $7$ colors: that is, we can separate the $51$ people into $7$ harmonious groups. We can do this recursively: 


*

*Pick some person involved in at most $6$ conflicts (that is, who is hated by at most $3$ people) and set them aside.

*Partition the remaining $50$ people into $7$ harmonious groups using this same algorithm.

*Put the person we set aside into a group that they have no conflicts with; this is possible because they have at most $6$ conflicts and we have $7$ groups.
This is best possible, since (as pointed out in the comments) the graph could contain a $K_7$: if among the first $7$ people numbered $1,2,3,4,5,6,7$, person $i$ hates $\{i+1,i+2,i+3\} \bmod 7$, then no two of these can be in the same group together. So we can't do better than $7$ groups.
A more general result can be found in this question.
