Past exam of the Probability, statistics and options II course of the University of Oxford / 2011 / R / R2 / c / Solution

Let $k=\chi (G)$. For $k\le 1$ the bound is immediate. Otherwise choose a vertex-minimal subgraph $H$ with chromatic number $k$. Each vertex has degree at least $k-1$ in $H$: if one had degree at most $k-2$, a $(k-1)$-colouring of the smaller graph obtained by deleting it could be extended to it using an absent neighbour colour, contradicting $\chi (H)=k$.

The graph $H$ has at least $k$ vertices. By the degree-sum identity,Solving the quadratic inequality gives