Lesson 1

We already know that there are triangle-free graphs with arbitrarily high chromatic number. Below we generalize this result: we will show that there are graphs with arbitrarily high chromatic number and not containing cycles of any given length. This seems even more surprising. Or it further demonstrates the non-locality of the chromatic number. Indeed, suppose the graph has no cycles of length, say, 100. Then consider the neighborhood of an arbitrary vertex with radius 50: consider the vertex itself, then its neighbors, then their neighbors—and so on, 50 times. Then this must form a tree: if it didn't, there would be a cycle of length at most 100. Thus, the radius-50 neighborhood of any vertex is a tree. Hence, it can be colored in two colors!