# 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
• @AbdulMalekAltawekji: Do you mean you don't understand why my hint is true, or you don't understand why it helps do the problem? – Micah Dec 12 '17 at 18:59
• If $G$ does not have at least 5 vertices of degree 6, it has at most 4 vertices of degree 6. If $G$ does not have at least six vertices of degree 5, it has at most 5 vertices of degree 5. If it doesn't have exactly the maximum number in both cases, it doesn't have enough vertices (you know it has nine). – Micah Dec 13 '17 at 5:20
• For how it helps, look at Hagen's hint. – Micah Dec 13 '17 at 5:20