Simple graph with n vertices has a pair of vertices of same degree

For n≥2, a simple graph with n vertices has a pair of vertices of same degree. In this post, we will prove this theorem on simple graphs. Before we do this, let us first recall a simple graph which is given below.

A graph is called a simple graph if there is only one edge between a pair of vertices. Let us now prove that a simple graph of n vertices have at least two vertices of same degree.

Simple Graph has Two Vertices of Same Degree

Theorem: A simple graph with n vertices (n≥2) must have at least one pair of vertices with the same degree.

Proof:

Let G be a simple graph with n vertices where n≥2.

Step 1:

Note that the minimum degree of a vertex of G is 0 (this vertex is an isolated vertex) and the maximum degree of a vertex of G can be n-1 (that is, this vertex is connected to all other vertices).

Step 2:

Therefore, each vertex of G can have a degree ranging from 0 to n-1. So there are n number of possibilities for the degrees of a vertex.

But, note that if G has a vertex of degree 0 then it cannot contain a vertex of degree n-1 and vice-versa. This is because the graph G has n vertices.

Step 3:

From step 2, we deduce that there are (n-1) number of possible degrees of a vertex of G. As the graph G has n vertices, so by Pigeonhole Principle, there are at least two vertices with the same degree.

Conclusion:

Therefore, we have shown that a simple graph of n vertices (n≥2) must have at least one pair of vertices with the same degree.

Related Articles:

Simple Graph with n Vertices and k Components have at most (n-k)(n-k+1)/2 Edges

Prove that a tree with n vertices has (n-1) edges

Homepage of Discrete Mathematics