If $G$ is a simple graph which has chromatic number $\chi(G)$ is it true to claim that there is a $(\chi(G)-1)$-regular induced subgraph?
I've been trying to prove it. It seems as though it should be true. There must be at least one vertex $v$ of colour $1$, in a $\chi(G)$ colouring of $G$, which cannot change colour. This would contradict that $G$ has chromatic number $\chi(G)$. So $v$ has at least a neighbour of every other colour $2,...,\chi(G)$. For each colour, at least one neighbour of $v$ which is that colour, can't change colour. If it could $v$ could change colour. Therefore, this neighbour must also have at least one neighbour of every other colour...and so. until eventually this chain of vertices, which are unable to change colour, will form an $(\chi(G)-1)$-regular induced subgraph.
Does any one know if this claim is true? Is there an obvious counter example? Could any one prove it?