Prove that in a simple graph with at least two vertices ther

Prove that in a simple graph with at least two vertices there exist two vertices with the same degree.

Solution

Let G be any nite simple graph with more than one vertex and |V_G| = 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 nd 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 nd two vertices of the same degree in G.