## Problem1G

Problem1G: Show that a finite simple graph with more than one vertex has at least two vertices with the same degree.

Solution: Suppose the simple graph has ${n}$ vertices. Since the largest degree of a vertex is ${\leq }$ ${n-1,}$ thus the sets of distinct degrees of the vertices belongs to ${\left\{ 1,\ldots ,n-1\right\} .}$ By pigeonwhole principle, there at least two vertices with the same degree.