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

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?

-
If neither of those things are true, $G$ has exactly $5$ vertices of degree $5$ and exactly $4$ vertices of degree $6$. Can you see why this is impossible? – Micah May 11 '13 at 19:39
Oh my goodness, thank you. Both to Micah and Hagen. – Evan May 11 '13 at 19:59