##### Theorem11.7Erdős

For every pair \(g,t\) of integers with \(g\ge3\), there exists a graph \(G\) with \(\chi(G)>t\) and the girth of \(G\) greater than \(g\).

At the outset of this chapter, we presented Erdős' original proof for the lower bound for the Ramsey number \(R(n,n)\) using counting. Later, we recast the proof in a probabilistic setting. History has shown that this second perspective is the right one. To illustrate the power of this approach, we present a classic theorem, which is also due to Erdős, showing that there are graphs with large girth and large chromatic number.

The *girth* \(g\) of a graph \(G\) is the smallest integer for which \(G\) contains a cycle on \(g\) vertices. The girth of a forest is taken to be infinite, while the girth of a graph is three if and only if it has a triangle. You can check the families of triangle-free, large chromatic number, graphs constructed in Chapter 5 and see that each has girth four.

For every pair \(g,t\) of integers with \(g\ge3\), there exists a graph \(G\) with \(\chi(G)>t\) and the girth of \(G\) greater than \(g\).

Experienced researchers are able to simplify the calculations in an argument of this type, as they know what can safely be discarded and what can not. Here's a quick tour of the essential steps. We want \(E(X_1)\) to be small, so we set \(n^se^{-ps^2}=1\) and get \(s=\ln n/p\). We want the number of small cycles to be about \(n\) so we set \((gp)^g=n\) and get \(p=n^{1/g-1}\). Finally, we want \(n=st\) which requires \(n^{1/g}=t\). The rest is just paying attention to details.