There are 3 colleges with $n$ students each. Any student knows $(n+1)$ students of the other colleges. Prove that there exists three students from different colleges who know each other (this doesn't have direction). A knows B implies B knows A i.e. the graph is undirected.
My work: Let the colleges be $X,Y,Z$. A student (say $a$) from college $X$ knows at least $\lfloor{\frac{n}{2} \rfloor}+1$. If one of the students that are known to $a$ in $Y$ knows a student in $Z$ and that student knows $a$ then we are done! But that is not always possible. There are too many cases. I can't take them all and become confused. Please help me.