Question

topic: graph theory

Question 5. Prove that every graph with at least two vertices contains two vertices with the same degree. Then for each n 2 2 give an example of a graph with n vertices which does not have three vertices of the same degree.

Answer 1

Let G be a finite graph with number of vertices n $\geq$ 2 .

For graph G there are two conditions which can arise.

Case 1-

Let the graph is connected.

Then as each vertex has unique degree, the degree must not exceed n-1 since if the degree of vertex becomes n, then there must exist more than 1 edge between two vertices. Thus making two vertices of same degree.

As the vertices have unique degree, by pigeonhole principle, there must exist two vertices with same degree.

Case 2-

The graph is disconnected.

We can use the similar logic as above. Since the graph is disconnected it must have two connected components.

Therefore, in this case degree of each vertex must not exceed n-2 otherwise it will become connected.

So again by pigeonhole Principle, there must exist two vertices of same degree.

Hence the proof

Also, it is very easy to draw a graph such that no three vertices have same degree.

For n=2,3 it is very easy to draw a graph such that no three verteices have same degree.

For n=4, draw a graph such that each vertex has degree 1,2,2,1. So this is required graph of degree 4.

For n=5, draw 1 more vertex in above graph and connect it with rest vertices. So the degree sequence will be 2,3,3,2,4

So for every n greater than 5 we can get such a required graph. By adding a vertex and then connecting it to rest vertices. This is known as converse of Havel-Hakimi algorithm.