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.

  • 5
    $\begingroup$ 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. $\endgroup$ – Pedro Tamaroff Sep 16 '13 at 22:52
  • 1
    $\begingroup$ How is this related to algorithms? $\endgroup$ – 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.


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.

  • $\begingroup$ That has nothing to do with the pigeonhole principle -- or for that matter, with the question. $\endgroup$ – Henning Makholm Sep 28 '13 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.