Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2008/a/3/d/solution

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!