How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?

I have found an interesting exercise in my introduction to graphs workbook:

Let $ad(G) = \frac{2\vert E(G)\vert}{\vert V(G) \vert}$ and $mad(G) = max\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}$.

Given a graph $G$ and a number $k \geq 3$, prove that if $\chi(G) > k \wedge mad(G) \leq k \Rightarrow \exists A \subseteq V(G)$ such that $[A]_{G}$ is $k - regular$.

I believe this can proved by contradiction:

Given a $G$ and $k$ for which the properties hold, we assume that $G$ has no induced subgraph $H$ that is $k - regular$. We then prove that if $\nexists H$ then at least one of the property is false and thus we contradict ourselves however I can't quite figure out the connection between $H$ and the mentioned properties.

How would you go about solving this?

Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:

• Show that $G$ has a vertex $v$ of degree smaller than $k$.

• Color $G - v$ using $k$ colors (by induction).

• Complete this to a $k$-coloring of $G$.

StackExchange Computer Science Q#16720, answer score: 3