Welcome to our community

Be a part of something great, join today!

Graph theory

Amer

Active member
Mar 1, 2012
275
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
Jan 30, 2012
43
Is this question complete? It seems truncated.
 

Amer

Active member
Mar 1, 2012
275
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
Feb 7, 2012
2,678
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.