I need help starting this proof in Graph Theory
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.