Please move this to the appropriate board, if this board isn't. I'm trying to really figure out how to start this proof. My hunch is that there will be 3 cases, but even then I don't know how/where to start. My thanks in advance!
A graph G has order n=2k+3 for some positive integer k. Every vertex o G has degree k+1, k+2, or k+3. Prove that G has at least k+3 vertices of degree k+1 or at least k+1 vertices of degree k+2 or at least k+2 vertices of degree k+3.
I'm pretty confident it uses the corollary that says:
Every graph has an even number of odd vertices.
I don't know if the k is the same for size and each of the cases.