[Math] Show that a graph with 9 vertices has at least five vertices of degree 6, or at least six vertices of degree 5.

Question

Let $G = (V, E)$ be a graph with nine vertices, such that each vertex has degree $5$ or $6$. Show that $G$ has at least five vertices of degree $6$, or at least six vertices of degree $5$.

My friend and I have been working on this question for the past two days and we have nothing. Any pointers or help?

Answer 1

Hint: The sum of all vertex degrees is twice the number of edges.