Paul Erdős was the first to prove the general result, using the probabilistic method.[4] More precisely, he showed that a random graph on n vertices, formed by choosing independently whether to include each edge with probability n(1 − g)/g, has, with probability tending to 1 as n goes to infinity, at most n/2 cycles of length g or less, but has no independent set of size n/2k. Therefore, removing one vertex from each short cycle leaves a smaller graph with girth greater than g, in which each color class of a coloring must be small and which therefore requires at least k colors in any coloring.