Abstract:
We give a new proof of the classical Erdos theorem on the existence of graphs with arbitrarily high chromatic number and girth. Rather than considering random graphs where the edges are chosen with some carefully adjusted probability, we use a simple counting argument on a set of graphs with bounded degree.