The Pigeonhole Principle in Graph Theory

Sometimes the most powerful ideas are the simplest. The Pigeonhole Principle is one of them — and once you see it, you’ll start noticing it everywhere.

What Is the Pigeonhole Principle?

Imagine you have 10 pigeonholes (small boxes) and 11 pigeons. You need to put every pigeon into a hole. No matter how you arrange them, at least one hole must hold 2 or more pigeons — there simply aren’t enough holes.

That’s the entire principle:

If you have more items than containers, at least one container must hold more than one item.

The General Version

More precisely: if $n$ items are placed into $k$ containers where $k < n$, then at least one container holds at least $\lceil n/k \rceil$ items.

Quick examples:

Example 1: Social Networks — Two People Always Have the Same Friend Count

The Problem

In a social network of 367 people, must at least two people have the same number of friends?

The Solution

Each person can have 0 to 366 friends (you can’t be friends with yourself).

Apply the same reasoning as before:

• If someone has 0 friends, nobody can have 366 friends (because at least one person is disconnected)
• If nobody has 0 friends, then 366 is the max possible and 0 is unavailable

Either way: only 366 distinct friend-count values exist for 367 people.

• Pigeons = 367 people
• Pigeonholes = 366 possible friend counts

Yes — at least two people must have the same number of friends. No matter how the network is structured.

Example 2: You Can’t Color 12 Vertices with 10 Unique Colors

The Setup

Suppose you want to color the vertices of a graph using 10 different colors, and you want every vertex to get a different color from every other vertex. Can you do it if your graph has 12 vertices?

No. Here’s why:

• Pigeons = 12 vertices
• Pigeonholes = 10 colors

Since there are more vertices than colors, at least $\lceil 12/10 \rceil = 2$ vertices must share the same color.

Visualizing It

The graph below has 12 vertices colored with only 10 colors. Nodes 1–10 sit on the outer ring, each with a unique color. Nodes 11 ★ and 2 share blue, and nodes 12 ★ and 1 share red — two forced collisions. The Pigeonhole Principle guarantees this: 12 vertices cannot all get distinct colors when only 10 are available.

The ★ nodes (11 and 12) are the extra vertices that force the color collisions — look for the matching colors on the outer ring.

Where This Matters

Example 3: In Any Graph, Two Vertices Always Share a Degree

This is one of the most elegant applications of the Pigeonhole Principle.

The Claim

In any graph with at least 2 vertices, at least two vertices must have the same degree.

You literally cannot build a graph where every vertex has a unique degree (except for the trivial one-vertex case).

Why This Seems Wrong at First

Take a graph with $n = 5$ vertices. Each vertex’s degree can be 0, 1, 2, 3, or 4 — that’s 5 possible values for 5 vertices. Shouldn’t we be able to assign each vertex a distinct degree?

The answer is no, and it comes down to one hidden constraint.

The Hidden Constraint

Degrees 0 and n-1 cannot both exist in the same graph. Here’s why — consider two cases:

Case 1: Some vertex has degree 0 (isolated)

A degree-0 vertex connects to nobody. So no vertex can connect to all n-1 others — the isolated vertex is unreachable. So degree $n-1$ is impossible.

Available degrees: $\{0, 1, 2, \ldots, n-2\}$ → only $n-1$ values.

Case 2: No vertex has degree 0

Every vertex has at least one connection, so degree 0 doesn’t exist.

Available degrees: $\{1, 2, 3, \ldots, n-1\}$ → again only $n-1$ values.

Now Apply Pigeonhole

In both cases:

• Pigeons = $n$ vertices
• Pigeonholes = $n-1$ available degree values

$n$ vertices, $n-1$ slots → at least two vertices must share a degree. Every time, no exceptions.

Concrete Walkthrough: 5 Vertices

Let’s try (and fail) to build a 5-vertex graph with all distinct degrees:

Attempt: degrees {0, 1, 2, 3, 4}

  Vertex A — degree 4 — must connect to B, C, D, E
  Vertex E — degree 0 — connects to nobody

  But A says it connects to E.
  And E says it connects to nobody.
  ✗ Contradiction!

Attempt: degrees {1, 2, 3, 4} — skip 0

  Now we have 5 vertices but only 4 degree values.
  By Pigeonhole Principle → at least 2 vertices share a degree.
  ✗ Impossible to make all distinct.

There’s no way out. The principle guarantees it.

Example 4: Party Handshakes

Question: At a party with 20 people, can each person shake a different number of hands?

Answer: No.

• Handshake counts range from 0 to 19 — that’s 20 values
• But 0 and 19 can’t coexist (same argument as degrees)
• So only 19 distinct counts exist for 20 people
• By Pigeonhole: at least two people shake the same number of hands

The Generalized Pigeonhole Principle

The basic version says at least one container has multiple items. The stronger version tells you exactly how many:

If $n$ items go into $k$ containers, at least one container holds $\lceil n/k \rceil$ items.

Application: How Many Vertices Share a Degree?

Theorem: In a graph with $n$ vertices and maximum degree $\Delta$, at least $\lceil n/(\Delta + 1) \rceil$ vertices share the same degree.

Example: A graph with 50 vertices, max degree 4:

• Possible degrees: 0, 1, 2, 3, 4 → 5 values
• At least $\lceil 50/5 \rceil = \mathbf{10}$ vertices share the same degree!

Connection to Ramsey Theory

The Pigeonhole Principle is the seed of Ramsey Theory — the study of how large a structure must be before patterns inevitably appear.

A Classic Result

In any group of 6 people, either 3 are all mutual friends, or 3 are all mutual strangers.

This is proved by applying the Pigeonhole Principle to the edges of the complete graph $K_6$ — color each edge red (friends) or blue (strangers), and use the principle to force a monochromatic triangle.

Why It’s Forced

Pick any one person — say A. They have 5 relationships, each either a friendship (red) or a stranger-ship (blue). By Pigeonhole with 5 edges and 2 colors: at least 3 edges from A must be the same color.

Say A has 3 red edges — to B, C, D. Now look at the edges between B, C, and D:

• If any of B-C, B-D, or C-D is red → that pair plus A forms a red triangle ✓
• If all of B-C, B-D, C-D are blue → B, C, D are all mutual strangers → blue triangle ✓

Either way, a monochromatic triangle is guaranteed. The graph below shows exactly this: A has 3 red friend-edges to B, C, D. Since B-C, B-D, C-D must all be blue to avoid a red triangle with A — and they are — the forced blue triangle B-C-D appears. A red triangle B-E-F also emerges from the remaining edges.

Red edges = friends 👫 · Blue edges = strangers 🚫 · Triangles B-C-D (blue) and B-E-F (red) are both monochromatic — neither can be avoided.

Common Mistakes

Mistake 1: Forgetting the Hidden Constraint

❌ “A graph with $n$ vertices has $n$ possible degrees (0 to n-1), so all vertices can have distinct degrees.”

✓ Degrees 0 and n-1 can’t coexist, leaving only n-1 possible values — not $n$.

Mistake 2: Not Identifying the Right Objects

Before applying the principle, ask yourself:

1. What are the pigeons? (the objects being distributed)
2. What are the pigeonholes? (the categories or slots)
3. Are there hidden constraints? (that reduce the number of available slots)

Practice Problems

Problem 1: Chromatic Number Bound

In a graph with 100 vertices where every vertex has degree at most 4, prove that 5 colors are always enough to color it so no two adjacent vertices share a color.

Problem 2: Tournament Out-Degrees

In a tournament (a directed complete graph where every pair of vertices has exactly one directed edge), can all vertices have distinct out-degrees?

Problem 3: Distances in a Graph

In a connected graph with $n$ vertices, fix any vertex $v$. Prove that at least two other vertices are at the same distance from $v$.

Summary

The deeper lesson: The Pigeonhole Principle doesn’t tell you where the collision happens — only that it must happen. The creative challenge is always in recognizing your pigeons and holes.

Test the principle yourself — build graphs in the interactive playground and see if you can escape the Pigeonhole Principle!