Existence of rainbow paths in graphs? Let $G$ be a graph, and let $c: V(G) \to \{1,\dots,k\}$ be a proper $k$-colouring of $G$. We say that a path $v_1 \dots v_k$ in $G$ is a rainbow path of this colouring if $c(v_i) = i$ for every $i \in \{1,\dots,k\} $. Now suppose that $k = \chi(G)$, the chromatic number of $G$; I am trying to determine whether or not a rainbow path exists for this colouring.
I don't really know where to start, though. If $k = 2$, then a rainbow path certainly exists; for the case $k = 3$, I've tried looking at cycles of odd length and wheels with an odd number of spokes and it seems that such graphs must always have rainbow paths as well, but I'm not sure how to generalize to general graphs with $\chi(G) = 3$ or to higher values of $k$.
Any help is appreciated!
 A: The answer is yes.
We may without loss of generality assume that $G$ is connected; otherwise we throw away each component with lower chromatic number, and consider every other component individually.
For $k=3$: Let $E_1$ be the set of all vertices with the color $1$. Let $E_2$ be the set of all vertices adjacent to a vertex in $E_1$ with the color $2$. If there is no such vertex, then all vertices in $E_1$ could be recolored to the color $2$, and we have a $(k-1)$-coloring of $G$; contradiction. Let $E_3$ be the set of all vertices adjacent to a vertex in $E_2$ with the color $3$. If there is no such vertex, then we could recolor $E_1$ to the color $2$ and $E_2$ to the color 3, and obtain a 2-colorable graph; contradiction. Therefore $E_1,E_2,E_3$ are nonempty, so we can find a rainbow path $e_1,e_2,e_3$ where $e_i\in E_i$.
This argument can be carried on for general $k$: Let us continue. Let $E_4$ be the set of vertices adjacent to $E_3$ which have the color $4$. If it were empty, then we could recolor $E_1,E_2,E_3$ to the colors $2,3,4$, respectively, and obtain a $(k-1)$-coloring of $G$; contradiction. We can define $E_5,\ldots,E_k$ analogously. When we are done, we can choose a rainbow path $e_1,\ldots,e_k$ where $e_i\in E_i$ for each $i$.
