The smallest possible $n$ is $7$. To show that a smaller $n$ is not enough, take $7$ senators $0, 1, 2, 3, 4, 5, 6$ such that senator $i$ hates senators $i+1, i+2, i+3 \pmod{7}$. Then in any pair of these senators, one hates the other, so no two can be together in a commitee, and we need at least $7$ commitees. To show that $7$ is enough, let $k=51$ and do induction on $k$. The base case is obvious. If the assertion is proved for $k$, take $k+1$ senators; there are exactly $3k+3$ instances of someone hating someone else, so by pigeonhole there's a senator hated by at most $3$ other senators. Take him out and put the other $k$ senators into $7$ good commitees (obviously we can do this by IH); now, since the left out senator is hated by at most $3$ people and hates exactly $3$, at most $6$ commitees are forbidden and there's at least one commitee for him, so we're done.

we have a generalization of it: for every directed graph that for every vertice of G outest degree is $\leq k$ we can partition the graph to $2k+1$ independent set. it can be easily prove by induction on number of vertices and with use of cancellation of the vertice with minimum inner degree.

MithsApprentice wrote: There are 51 senators in a senate. The senate needs to be divided into $n$ committees so that each senator is on one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does not necessarily hate senator A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee. We prove a generalized version of the problem : Generalized version wrote: Let $G$ be a DG on $n$ vertices such that no vertex has an out-degree greater than $k$. Show that the vertices of $G$ can be colored in $2k+1$ colors such that no two vertices of the same color are connected. Proof: We proceed by induction on $n$. The base case for $n=3$ is trivial. So suppose that the assertion is true for a graph on $n$ vertices. Now consider a graph on $n+1$ vertices such that no vertex has an out-degree greater than $k$. Notice that this graph, $G'$, must contain a vertex having in-degree $\le k$ i.e. $\exists \nu \in \text{V} (G')$ such that $\delta \nu \le 2k$. If not, then notice that the total number of edges would be greater than $(n+1)k$, a contradiction to the assertion. Thus, we can partition $G'$ into $\nu \cup G'\setminus \nu$. By the induction hypothesis,$G'\setminus \nu$ can be colored in $2k+1$ colors. Now $\nu$ has at most $2k$ neighbors in the other set and hence at least one color will always be available for $\nu$ different from that of its neighbors.