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.
Best Answer
It is tacitly assumed that the graph $G$ is finite and contains no loops or double edges. Otherwise it is easy to give counterexamples.
Let $v_0$ be the number of isolated vertices, and denote by $v'$ the number of vertices of degree $\geq1$. When $v_0=2$ we are done. Otherwise $v'\geq1$, and $d_\max$, the maximal occurring degree, is $\geq1$. Since a vertex of maximal degree is connected to $d_\max$ other nonisolated vertices we have $$v'\geq d_\max+1\ .$$ The $v'$ vertices of degree $\geq1$ can have degrees from $1$ to $d_\max$ inclusive. As $v'>d_\max$ we can conclude by the pigeon hole principle that two of them have to have the same degree.