Proof: By Induction

By hypothesis, $G$ is a simple graph with the maximum vertex degree $d$.
We will prove $\chi(G)\le d+1$ by induction on $d$.
Base case $n=1:$
- For a simple graph $K_1$ with one vertex, the chromatic number is trivially $\chi(K_1)=1$ and $d=0$, thus $\chi(K_1)\le 0 + 1.$
Induction step $n\to n+1:$
- Let $G$ be a simple graph with $n$ vertices $v_1,\ldots,v_n$ and maximum vertex degree $d$ and assume, $\chi(H)\le d+1$ for all simple subgraphs $H\subset G$ of $G$ with fewer than $n$ vertices.
- We construct a subgraph $H_i=G[v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_n],$ obtained from $G$ by removing any vertex $v_i$ ($i\in{1,\ldots,n}$ and its incident edges.
- By induction assumption, $\chi(H_i)\le d+1$ for all $i=1,\ldots,n.$
- Since $v_i$ has at most $d$ neighbours, these vertices can be colored with at most $d$ colors.
- From the coloring of any given subgraph $H_i,$ we can therefore obtain the coloring of $G$ by selecting a $(d+1)$st color distinct to the $d$ colors of the neighbours of $v_i$.
- It follows $\chi(G)\le d+1.$
By induction, it follows that the statement is true for all simple graphs with $n$ vertices, $n\ge 1.$
∎

Thank you to the contributors under CC BY-SA 4.0!

Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000