Prove that if the chromatic color of G k then for every kco

Prove that if the chromatic color of (G) = k then for every k-coloring of G there is a path of length k- 1

in G with different colors of vertices.

Let v be the vertex of G so that d(v)<(k-1)

let G be a k chromatic graph and let H be a k-critical graph of G, then H-v has a (k-1) coloring.

as v has atmost k-2 neighbours, these neighbours use at most k-2 colours in this (k-1) colouring of H-v,

Now colour v with the unused colour and this gives a (k-1) colouring of H

so every vertex v of H has degree atleast (k-1) in H and hence also in G.