**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 vertices. Since the largest degree of a vertex is thus the sets of distinct degrees of the vertices belongs to By pigeonwhole principle, there at least two vertices with the same degree.

### Like this:

Like Loading...

*Related*