Let G be an undirected graph with at least two vertices. Then there exist distinct vertices v and w in G that have the same degree.

Question

The “pigeonhole principle” states that if n+1 objects (e.g., pigeons) are to be distributed into n holes then some hole must contain at least two objects. This observation is obvious but useful.

Employ the pigeonhole principle to prove the following:

Claim: Let G be an undirected graph with at least two vertices. Then there exist distinct vertices v and w in G that have the same degree.

Thank you so much for all your help, a couple of problems on this homework were unlike anything we've done in class thus far. I think they're supposed to be an easy concept questions but I'm struggling.

Answer 1

You have two pigeons (vertices) so that pigeon can only have one pigeon friend (edge to another vertex). But you also have two pigeons, so two pigeons and one pigeon friend imply they are friends of each other.

Inductively, you have n pigeons with n-1 pigeon friends.