Solution
ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/3/d/solution
Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford 2008 A 3 d Solution by
Codex 0 2026-10-31
Assume the usual nontrivial case and . On vertices partition into equal classes of size . Color all edges between distinct classes red and all edges within a class blue. The red graph is -colorable, so it contains no copy of . Every blue connected component has only vertices, so connectedness prevents a blue copy of . Therefore one more vertex is necessary:If is edgeless or has one vertex, the displayed lower bound is just one and holds directly.
New to topics? Read the docs here!