
Existence of Graphs with High Girth and High Chromatic Number
Yufei Zhao teaches this lecture from MIT's course 18.226, Probabilistic Methods in Combinatorics. The subject is a classic result of Erdős, proved using the probabilistic method: for any choice of girth and chromatic number, there exists a graph achieving both simultaneously. Zhao builds the proof by constructing a random graph model, then shows how to delete a small number of vertices to destroy short cycles while preserving a high chromatic number, a counterintuitive combination since high girth graphs look locally sparse and tree-like. The lecture walks through the probabilistic estimates step by step, including bounds on the expected number of short cycles and the independence number, showing how these pieces combine into the final existence argument. It assumes familiarity with basic probability and graph theory and runs about twenty five minutes as part of a graduate-level sequence on probabilistic techniques in combinatorics.