= Solution
Let $k=\chi(G)$. For $k\leq1$ 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,
$$
2m\geq2|E(H)|=\sum_{v\in H}\deg_Hv\geq(k-1)|V(H)|\geq k(k-1).
$$
Solving the quadratic inequality gives
$$
\boxed{\chi(G)=k\leq\frac12+\sqrt{2m+\frac14}.}
$$
Back to article page
