Proving Degrees of Vertices in Graph G

[Amer]

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

 

[janvdl]

Is this question complete? It seems truncated.

 

[Amer]

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]

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.

 

[CellCoree]

I would like to begin by stating that the given statement is a well-known and established fact in the field of graph theory. The degree of a vertex in a graph G refers to the number of edges incident to that vertex. Therefore, the given statement is essentially stating that in a graph G with an odd number of vertices, the degree of each vertex can only be either n+1 or n+2.

To prove this statement, let's consider a graph G with an odd number of vertices, 2n+1. We know that the sum of degrees of all vertices in a graph is equal to twice the number of edges (Handshaking Lemma). In other words, the sum of degrees of all vertices in G is equal to 2|E|.

Now, let's assume that the degree of each vertex in G is either n+1 or n+2. This means that the sum of degrees of all vertices in G can be written as follows:

(n+1) + (n+2) + (n+1) + (n+2) + ... + (n+1) + (n+2)

= (n+1)n/2 + (n+2)n/2

= (n^2 + 3n)/2

Since we know that the sum of degrees of all vertices in G is equal to 2|E|, we can equate the two expressions and solve for |E| as follows:

2|E| = (n^2 + 3n)/2

|E| = (n^2 + 3n)/4

Since n is an integer, n^2 + 3n is always divisible by 4. Therefore, |E| is also an integer. This means that the number of edges in G must be an even number.

However, we know that in any graph, the number of edges must be an integer. Therefore, the number of edges in G must be either an even number or an odd number. But we have just shown that the number of edges in G must be an even number. This means that the number of edges in G cannot be an odd number.

But if the number of edges in G is not an odd number, then it must be an even number. And if the number of edges in G is an even number, then it must be divisible by 2. This means that the number