HMMT 2009 T3

A graph is finite if it has a finite number of vertices. (a) $[6]$ 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$.