There are $17$ people in a room. Every two people are mutually friends, enemies, or strangers. Prove there must be three people all of whom have the same relationship.
I think this is a graph coloring problem. It is a problem from my book but I am struggling to solve it. I tried to do many things, like considering the chromatic polynomial of the graph. But I have had no luck. I am really not sure how to approach the problem and will appreciate any help
Note that the graph of relationships is $K_{17}$. This is an edge-coloring exercise. Note that any given vertex $v$ is connected to $16$ other vertices, so by the pigeonhole principle and without loss of generality, $v$ has at least $6$ friends. Note that these $6$ friends can't be friends with each other.
Consider the subgraph of $6$ vertices of these friends and all of their relationships (either stranger or enemy). Consider vertex $w$. By pigeonhole and WLOG, $w$ has at least $3$ enemies. These three enemies must all be strangers with each other, which is a contradiction, so we are done.