In a group of nine people, one person knows two of the others, two people each know four others, four each know five others, and the remaining two each know six others. Show that there are three people who all know each other.
Consider a graph with $9$ vertices such that $1$ vertex has degree $2$, and $2$ have degree $4$, $4$ have degree $5$, and $2$ have degree $6$. Note that by the Handshake lemma, we can sum this up to make it equal to twice the number of edges (denoted $q$):
$$ \begin{equation} \Sigma_{i=1}^9deg(v_i)=2+2(4)+4(5)+2(6)=42=2q \end{equation} $$
This implies that the number of edges is $21$. We observe that this number is precisely $3p-6$, where $p$ is the number of vertices. Because this inequality holds, the graph of the people is maximal planar and thus contains a $3$-cycle. That is, there exist $3$ people who all know one another.
Special thanks to Jaden (Hamilton, ON), Olivier Massicot (Champaign, IL), and Ravi Dayabhai (California) & Conrad Warren (Canada, Alberta) for submitting a solution to this challenge problem.