In any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree?

Question

Recently, I am reading the book [1]. I am trying to solve the following problem:

1.2 Pigeons and holes. Properly speaking, we should call our representation of Königsberg a multigraph, since some pairs of vertices are connected to each other by more than one edge. A simple graph is one in which there are no multiple edges, and no self-loops.

Show that in any finite simple graph with more than one vertex, there is at least one pair of vertices that have the same degree. Hint: if $n$ pigeons try to nest in $n - 1$ holes, at least one hole will contain more than one pigeon. This simple but important observation is called the pigeonhole principle.

The following is my attempt to solve the problem: Let $G$ be a finite simple graph that has $N_V$ vertices and $N_E$ edges. Because each edge connects two vertices, the number of total degrees is $2 N_E$. Let $d_i$ be the degree of the $i$th vertex for $i = 1, 2, ..., N_V$, then $$\sum_{i = 1}^{N_V} d_i = 2 N_E. \tag{1}$$ On the other hand, we know $$0 \leq d_i \leq N_V - 1. \tag{2}$$ When $d_i = 0$, it means that the $i$th vertex does not connect with any other vertices. A vertex can connect with at most $N_V - 1$ vertices.

Then I don't know how to continue. Could any one please tell me the correct solution? Thanks in advance.

Note: It is not my homework. I am just interested in solving the problem.

Reference:

[1] C. Moore and S. Mertens, The Nature of Computation, Oxford University Press, 2015.

Answer 1

This one is a bit tricky! Here is the idea. We would like to use the pigeonhole principle. However, there are $n$ vertices and $n$ possible degrees $0,\ldots,n-1$, so the pigeonhole principle allows the situation in which each degree appears exactly once. We can flatly rule it out for values of $n$ which are of the form $4m+2$ or $4m+3$ using the handshake lemma, which states that the sum of the degrees is even, but what about the general case?

It turns out that to solve the general case we don't even need the handshake lemma. The following observation suffices (and explains why we need $n>1$):

If $n > 1$ then a graph cannot contain both a node of degree $0$ and a node of degree $n-1$.