Proof of Degree 5/6 for Graph Theory: Pigeonhole Principle

[smiles988]

1. Suppose a graph has nine vertices each of degree 5 or 6. Prove that at least five vertices have degree 6 or at least six vertices have degree 5.

Homework Equations

3. I'm pretty sure that I need to use the Pigeonhole Principle to solve, but don't know where to go from there.

 

[HallsofIvy]

Suppose the graph has fewer than 5 vertices of degree 6. How many vertices does that leave? What degree do those vertices have?