I'm working on a Pigeon Hole problem as part of my homework and I'm having difficulty coming up with the actual mathematical rationale behind my explanation. The problem is as follows:

There are 6 circles and each circle is directly connected to zero or more other circles. Show that there are at least two circles that are connected to the same amount of circles, i.e. have the same amount of connections.

Visually, I can see how this works, but I'm having trouble verbalizing. Would the pigeonholes here be the amount of connections (0 connection, 1 connection, 2 connection ... up to 5) and the pigeons the actual connections themselves after attempting to connect the circle accordingly? Any clarification would be great and I've provided an example below:

Two examples, where the numbers inside represent the amount of connections


1 Answer 1


The six pigeons (circles) could match the six holes (counts from $0$ to $5$), but then every hole must be occupied. In particular one circle is connected to $0$ and another to $5$ (i.e., all) circles - contradiction.


Your Answer

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