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

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?

• As a side note, the commonly accepted terminology for "definite" is "vertex-critical", or "$k$-vertex-critical" if $k$ is known. – Misha Lavrov Nov 13 '18 at 18:38

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.