Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 11 / 1 / i

Use the random alteration method. Take arbitrarily large $n$ divisible by $2k$, and sample a binomial random graph with edge probability $p=n^{-1+1/(2g)}$. Let $Z$ count cycles of lengths $3,\dots ,g-1$. For each length $\ell$, its expected count is at most $(np{)}^{\ell }/(2\ell )$, soThe sum is empty if $g=3$. By the Markov inequality, $Z\le n/2$ with probability tending to one.

Set $s=n/(2k)$. The expected number of independent $s$-vertex sets isbecause the negative exponent has order $n^{1+1/(2g)}$, dominating the term of order $n$. Thus with probability tending to one there is no independent set of size $s$.

Choose a realization having both properties. Delete one vertex from each of its short cycles, using at most $Z$ deletions. The induced remaining graph $H$ has at least $n/2$ vertices and girth at least $g$. Deletion cannot create a new independent set, so $\alpha (H)\le s-1$. Every colour class is independent, givingIn particular a graph of the required girth and chromatic number exists. This proves graphs of arbitrarily high girth and chromatic number rather than invoking that existence theorem.