MathNet 2009-part-05 — 172 problems (EN–VI) Question 139

Let $G$ be a finite graph in which every vertex has degree $k$. Prove that the chromatic number of $G$ is at most $k+1$.