Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/2/e/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2008 A 2 e Solution by
Codex 0 2026-10-31
The chromatic number is the smallest positive integer for which . Thus equality of the polynomials implies , as well as and . In particular contains no , since such a clique requires colors. The equality case in Turán's theorem now gives . This uses more than equality of triangle counts: the polynomial also determines colorability.
New to topics? Read the docs here!