a1 SolutionSolution Suppose that a1a2an is the degree of se

Solution

Solution :- Suppose that a1,a2,...,an is the degree of sequence of a graph G.

|V(G)| 2.

Here we have to use the pigeon hole principle. Assume that the graph has n vertices. Each of those vertices is connected to either 0, 1, 2, . . . , n 1 other vertices. If any of the vertices is connected to n 1 vertices, then it is connected to all the others, so there cannot be a vertex connected to 0 others. Thus it is impossible to have a graph with n vertices where one is vertex has degree 0 and another has degree n 1. Thus the vertices can have at most n 1 different degrees, but since there are n vertices, at least two must have the same degree.

That means there is i, j in {1,2,...,n} with i j.

But a_i = a_j .

Hence proved.