# Graph theory

#### Amer

##### Active member
The degree of every vertex of a graph G of order $2n+1 \geq 5$ is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertex

Last edited:

#### janvdl

##### Member
Is this question complete? It seems truncated.

#### Amer

##### Active member
The degree of every vertex of a graph G of order $2n+1 \geq 5$ is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertex of degree n+1

#### Opalg

##### MHB Oldtimer
Staff member
The degree of every vertex of a graph G of order $2n+1 \geq 5$ is either n+1 or n+2. Prove that G contains at least n+1 vertices of degree n+2 or at least n+2 vertices of degree n+1
Try using an argument by contradiction. Suppose that there are $x$ vertices of degree $n+1$, and $y$ vertices of degree $n+2$, and suppose that the result is false. Then $x\leqslant n+1$ and $y\leqslant n$. But $x+y=2n+1$. It follows that we must have $x=n+1$ and $y=n.$ By counting the number of edges in the graph, show that this leads to a contradiction.