The *girth* of a graph is the size of its smallest cycle. For instance, any cube or hypercube has girth 4 (and any bipartite graph will of course have a girth that is even or infinite).

A celebrated theorem of Pál Erdős states that there exist graphs with arbitrarily large girth and chromatic number. This theorem was the basis of the probabilistic method.