What does the pigeonhole principle have to do with graph theory?

Question

I am currently trying to teach myself graph theory, and in every book I've read the pigeonhole principle inevitably comes up. I understand the concept well enough, but what I fail to grasp is what a counting argument has to do with graph theory. What applications does the pigeonhole principle have in graph theory? Why is it so important?

Thank you so much for your help!

Answer 1

Here's an example.

Suppose a finite directed graph $G = (V, E)$ with at least one node has the property that for all nodes $n$, there is some edge $(n \to m) \in E$. Then there is a cycle in $G$.

Proof: Let $k = |V|$. Take some node $n \in V$. Pick a sequence $n_0, \ldots, n_k$ such that $n_0 = n$ and for all $m < k$, there is an edge $n_m \to n_{m + 1}$.

By the pidgeonhole principle, there must be some $0 \leq i < j \leq k$ such that $n_i = n_j$. Then $n_i, n_{i + 1}, \ldots, n_{j - 1}, n_j$ is a cycle. $\square$

This proves that nonempty finite directed acyclic graphs must have some node $n$ with no edges going out of it. Of course, we can take the dual graph to get that finite directed acyclic graphs must have some node $n$ with no edges going into it either. This is useful for proving that topological sorting is possible.