Exercise 1808Combinatorics › Pigeonhole principleOlympiadAdded 3 Nov 2026

Graph theory via pigeonhole

#pigeonhole#graph#degree

Statement

Show that any simple graph on $n\ge 2$ vertices has two vertices of the same degree.

Hint

Degrees in $\{0,\ldots,n-1\}$ , but $0$ and $n-1$ cannot both occur.

Show solutionHide solution

Degrees. Each degree is in $\{0,\ldots,n-1\}$ .

Exclusion. A vertex of degree $0$ is isolated; a vertex of degree $n-1$ is adjacent to all. Both cannot occur simultaneously.

Pigeonhole. So at most $n-1$ distinct degrees among $n$ vertices: two coincide.

Conclusion. Any graph has two vertices of the same degree.