Existence of Graphs with High Girth and High Chromatic Number

Learn about the probabilistic method in combinatorics through a lecture that demonstrates Erdős' groundbreaking proof showing the existence of graphs with both arbitrarily high girth and chromatic number. Explore this 25-minute mathematics lecture from MIT's Probabilistic Methods in Combinatorics course, where Professor Yufei Zhao walks through the classic application of probabilistic techniques to graph theory, showcasing an elegant solution to what initially appears to be a counterintuitive mathematical property.