Graph Theory - Degree of vertices proof Here's a problem I've been assigned in my graph theory class:
The degree of every vertex of a graph $G$ of order $2n+1\ge5$ is either $n+1$ or $n+2.$ Prove that $G$ contains at least $n+1$ vertices of degree $n+2$ or $n+2$ vertices of degree $n+1.$ 
I could use some help getting started with this one. My first thought is to utilise the first theorem of Graph Theory, but doing so hasn't led to anything useful. Thanks.
 A: Let $x_1$ be the number of vertices with degree $n+1$, $x_2$ be the number of vertices with degree $n+2$.
For the sake of contradiction, assume that $x_1 < n+2$ AND $x_2 < n+1$.
Thus $x_1 \leq n+1$, $x_2 \leq n$. We know that $x_1 + x_2 = 2n+1$. This equality only holds when $x_1 = n+1$ AND $x_2 = n$.
Thus the sum of degree across all nodes is
$$
(n+1)(n+1) + (n)(n+2) = 2n^2 + 4n + 1
$$
Which is clearly odd. However, the sum of all degrees in a graph must be even. Contradiction.
Thus $x_1 \geq n+2$ OR $x_2 \geq n+1$
A: Proof (By Contradiction): Suppose the graph has less than n+1 vertices of degree n+2 and less than n+2 vertices of degree n+1 (i.e., there are at most (n+1)-1=n vertices of degree n+2, and at most (n+2)-1=n+1 vertices of degree n+1). Then the sum of all degrees is at most n(n+2)+(n+1)(n+1)=n^2+2n+n^2+2n+1=2n^2+4n+1. By the first theorem of graph theory, this is 2m, where m is the size of G. The size of G is unknown, but it can be no greater than if G is a complete graph. The complete graph has size z(z-1)/2, where z is the order; so if G is complete, then it has size {(2n+1)[(2n+1)-1]}/2 = (4n^2+2n)/2. So the sum of all degrees is 2n^2+4n+1 = 2m = 4n^2+2n. But 2n^2+4n+1 > 4n^2+2 for all n≥2; this is a contradiction. Any other such graph that is not complete will have a size less than that of this complete one. Thus they will lead to contradictions as well. Therefore G contains at least n+1 vertices of degree n+2, or at least n+2 vertices of degree n+1. QED.
Is this reasonable? 
