Pigeonhole Principle

If there are $n$ boxes and $m$ pigeons (where $m > n$), then at least one box must contain $\lceil \frac{m}{n} \rceil$ pigeons.

For a graph with $n \ge 2$ vertices, there exist 2 vertices with the same degree.