Question

Show that if G is a graph with n ≥ 2 vertices then G has two vertices with the same degree.

Answer 1

Let G be any finite simple graph with more than one vertex and |VG| = n ≥ 2. First, we notice
that the maximal degree of any vertex in G is less than equal n − 1. Also, if our graph G is not connected,
then the maximal degree is strictly less than n − 1.
Case 1: Assume that G is connected. We can not have a vertex of degree 0 in G, so the set of vertex degrees
is a subset of S = {1, 2, · · · , n − 1}. Since the graph G has n vertices, by pigeon-hole principle we can find
two vertices of the same degree in G.
Case 2: Assume that G is not connected. G has no vertex of degree n − 1, so the set of vertex degrees is
a subset of S' = {0, 1, 2, · · · , n − 2}. By pigeon-hole principle again, we can find two vertices of the same degree in G.