A class of 37 is to be divided into teams, and each student in the class must be a member of exactly one team. However, each student dislikes three of their classmates. Dislike between students need not be mutual. How many teams must be created so that no student is the teammate of someone they dislik?
I have no idea about this problem which seems trick. Could anyone give some hints? Thanks!
On
If we draw the directed graph with vertices players and an arrow from $p$ to $q$ iff $p$ dislikes $q$, then $d_{\text{out}}(v) = 3$ for all vertices and $|V|=37$. A team assigmnent is a vertex colouring where two endpoints of an arrow must have a distinct colour.
I don't know any theorems on colouring numbers of directed graphs in relation to (out-)degrees, though. But you might?
We cannot answer this question without further information.
On one extreme case, if each boy only dislikes girls and vice versa, 2 teams suffice (boys vs. girls).
In the worst case, you need 7 teams: numbering 7 of the kids $0, \ldots, 6$ and letting kid $i$ dislike kids $i+1, i+2, i+3$ (modulo 7) gives a copy of $K_7$, which requires 7 colors (teams) just to satisfy those 7 kids.
However, 7 teams is always enough by Brooks' theorem.Edit: Misha Lavrov in the comments correctly points out that my application of Brooks' Theorem was incorrect. He offers an alternative explanation: the (symmetrized) dislike graph is 6-degenerate, and by the information given on that page (specifically the equivalence of the two historical definitions) it is easy to see that this makes the graph 7-colorable.