Pigeonhole Principle

If $m$ objects are placed into $n$ containers where $m > n$, at least 1 container holds $\ge \lceil \frac{m}{n} \rceil$ objects.

Graph Degree Corollary

For any simple graph with $n \ge 2$ vertices, at least 2 vertices share the same degree.

Applications in Graph Theory

Paths in Dense Graphs

In any graph where every vertex has degree $\ge \lceil \frac{n}{2} \rceil$, a Hamiltonian path exists. The pigeonhole argument shows that any 2 non-adjacent vertices share enough neighbors to force connectivity.

Ramsey Numbers

Ramsey theory uses pigeonhole to prove monochromatic substructures must exist in large enough graphs. The classic result: in any 2-coloring of the edges of $K_6$, there is a monochromatic triangle.