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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: