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.