# Pigeon Hole Principle Algorithm

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 their supposed to be easy concept questions but I'm struggling.

• Which are you "pigeonholes"? Which are your "pigeons"? That's a start. In fact, if you can answer this, you can probably answer your question. – Pedro Tamaroff Sep 16 '13 at 22:52
• How is this related to algorithms? – lhf May 28 '14 at 16:00

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.