Graphs and pigeonholes
Gargano, Michael L. (2001) Graphs and pigeonholes. In: Robert J. Bumcrot Festschrift, 11 May 2001, Hofstra University.
Full text available as:
Sometimes the pigeonhole principle (PHP) is used to prove a result in graph theory. The following is a famous, well-known example: (Ramsey's Theorem) If the edges of a K6 are colored with red and blue then there is a K3 subgraph which is either all red or all blue. There are many other elegant applications of the pigeonhole principle. Presented here are some novel graph theory interpretations of a few of these PHP results.
Repository Staff Only: edit this item