= Solution
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,\ldots,g-1$. For each length $\ell$, its expected count is at most $(np)^\ell/(2\ell)$, so
$$
\mathbb EZ\le\sum_{\ell=3}^{g-1}\frac{n^{\ell/(2g)}}{2\ell}=o(n).
$$
The 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 is
$$
\binom ns(1-p)^{\binom s2}
\le2^n\exp\left(-\frac{p s(s-1)}2\right)\longrightarrow0,
$$
because 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, giving
$$
\chi(H)\ge\frac{|V(H)|}{\alpha(H)}\ge\frac{n/2}{s-1}>k.
$$
In particular \b[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.
Back to article page
