Prove that each graph with chromatic number $k$ has a definite induced sub-graph with chromatic number $k$.

Question

A graph with chromatic number k is definite if for each vertex $v$, $ChromaticNumber(G-v) < k$. Prove that each graph with chromatic number $k$ has a definite induced sub-graph with chromatic number $k$.

Any idea how can i start the proof?

Answer 1

Let $S$ be a maximal set of vertices such that $G \setminus S$ is $k$-colorable (but not $(k-1)$-colorable) but $G \setminus S'$ is $k'$-colorable for some $k' < k$. There clearly exists such an $S$ as removing all but $k-1$ vertices will make the graph $k'$-colorable for some $k' < k$ [make sure you see this indeed implies existence of such an $S$]

Then $G \setminus S$ is definite.