1

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.

user1176409
  • 1
user95227
  • 115
  • 6
    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 Sep 16 '13 at 22:52
  • 1
    How is this related to algorithms? – lhf May 28 '14 at 16:00

2 Answers2

2

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.

Christian Blatter
  • 226,825
-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.

Don Larynx
  • 4,703