A famous theorem of P. Erdős ¹.

Theorem 1   For any natural numbers and , there exists a graph with chromatic number and girth .

Obviously, we can easily have graphs with high chromatic numbers. For instance, the complete graph trivially has ; however (for ). And the cycle graph has , but

Instead of envisaging, Erdős' proof shows that, in some appropriately chosen probability space on graphs with vertices, the probability of choosing a graph which does not have and tends to zero as grows. In particular, the desired graphs exist.

This seminal paper is probably the most famous application of the probabilistic method, and is regarded by some as the foundation of the method.² Today the probabilistic method is a standard tool for combinatorics. More constructive methods are often preferred, but are almost always much harder.

Footnotes

...os ¹

See the very readable P. Erdős, Graph theory and probability, Canad J. Math. 11 (1959), 34-38.

... method.²

However, as always, with the benefit of hindsight we can see that the probabilistic method had been used before, e.g. in various applications of Sard's theorem. This does nothing to diminish from the importance of the clear statement of the tool.