[Math] Upper bound for chromatic number: $\chi (G) \le 1 + \max\{ \delta (H):H$ is induced subgraph of $G\} $

Question

I'd love a hint in this problem, because don't know where to start.
For any graph G it follows:
$$\chi (G) \le 1 + \max\{ \delta (H):H \text{ is induced subgraph of } G\} $$
where $\delta (H) = \min \left\{ {{d_H}(x):x \in V\left( G \right)} \right\}$

Answer 1

Hint: Let $d=\max\{\delta(H):H\text{ is induced subgraph of }G\}.$ Assume for a contradiction that $G$ is not $(1+d)$-colorable. Let $H$ be a minimal induced subgraph of $G$ which is not $(1+d)$-colorable. Now, every proper subgraph of $H$ is $(1+d)$-colorable. Moreover, $H$ has a vertex $v$ of degree $\le d.$ Can you get a contradiction from that?