In a $78$ member company everyone knows at least $5$ others. We sit them around 6-person tables. Prove that in every case there is a seating when at least at one table everybody knows his neighbors.
I think it's a proof by contradiction. Assume that the graph where the vertices are the people and the edges are the relation has no $6$ long cycle. How does it limit the sum of the degree?