There are 25 students in the class. It is known that among any three of them, two know each other. Show that there is a person who knows at least 12 other people.
Thoughts: I know this is true since I have been trying to find counterexamples. But I don't know how I can use the pigeonhole principle to relate it to this question.
Hint: Prove the contrapositive. Assume that each student knows at most 11 others. Pick a student, and then pick a second student not known to the first student. Then pick a third student...