Graph theory question Prove that in any graph with two or mo

Graph theory question

Prove that in any graph with two or more vertices, there must exist at least two vertices having the same degree.

Solution

Suppose you have a simple graph with n vertices. Since the graph is simple, an edge leaving a vertex has only n-1 places to go (since it can\'t come back to itself or we would have a loop) and it can\'t go to any of those places twice (or we would have a multi-edge). Hence 0<=d(vi)<=n-1.
Notice also that in a simple graph we cannot have both a vertex with degree 0 and a vertex with degree n-1 since having a certex with degree n-1 means that vertex is adjacent to every other vertex and hence we cannot have a vertex which does is not adjacent to any other vertices.
Suppose each d(vi) is distinct. Now in light of the previous notes, the degrees of the first n-1 vertices are either:
0, 1, 2, .... n-2
or
1, 2, 3, ... n-1.
In the first case the degree of the nth vertex must be in [0,n-2]. In the second case, the degree of the nth vertex must be in [1,n-1]. Hence, in either case, the degree of the nth vertex is equal to one of the degrees already on the list.
Therefore, in a simple graph with at least two vertices, at least two of the vertices must have the same degree.