Using Pigeonhole Principle for a graph proof

Question

Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is connected. Your proof must work for any graph, even those in which some vertices are isolated.)

I don't have any idea how to do this. Any advice?

Answer 1

Suppose we have $n$ vertex and $\deg(v_i)$ denotes the degree of vertex. Notice that $\deg(v_i)\in \{0,1,\ldots,n-1\}$.

Now, Assume not,

That means that $\deg(v_i)$ is one to one function from vertex set to $\{0,1,\ldots,n-1\}$ since both of them have $n$ element then it must be also onto.

There exist $i,j$ such that $\deg(v_i)=0$ and $\deg(v_j)=n-1$ which is a contradiction. Since if one vertex has no connection the other vertex has at most $n-2$ connections.

Answer 2

I've got another way, feel free to correct me.

Suppose you have a graph with $n$ vertices. At first, the possible options for a vertex's degree would be $\{0, 1, \ldots, n-1\}$. But now notice that if one of your vertices have degree 0, there is no way for other to have degree $n-1$, and vice versa (since there would be one vertex connected to the rest and an isolated one, which is not possible). Therefore, your vertices have only two sets as options for their degrees: $\{1, \ldots, n-1\}$ or $\{0, \dots, n-2\}$, and since there are $n$ vertices and $n-1$ options no matter which set they are taking their degrees from, we can use the pigeonhole principle and conclude that at least two vertices will have the same degree.

Answer 3

The question needs to assume the graph is simple because otherwise:

Degrees are 0 and 2.