Discussion: This student makes a creative use of the pigeonhole principle to obtain this result. In the absence of an isolated vertex (one without any connection to another vertex, a vertex of degree zero) the possibilities for the degree of a vertex is 1,2, . . . , n-1 (since a vertex cannot be connected to itself). Thus, two vertices must have the same degree, that is, the same number of neighbors.

Click the image to the left to bring up an enlarged copy of the solution.