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. 2. Relevant 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.