# Math Help - Paths in Coloured Graphs

1. ## Paths in Coloured Graphs

Suppose $\chi(G)=k$ and $c:V(G) \rightarrow \{1,\ldots,k\}$ is a proper $k$-colouring of $G$. Must there be a path $x_1 \ldots x_k$ in $G$ with $c(x_i)=i$ for each $i$?

I've been trying to find a counter-example without any luck (but on the other hand can't come up with a proof either...)

2. Take a look at the Gallai-Roy-Vitaver theorem and its corollaries. Apparently, a proof can be found in this article but you might be better to find the original somewhere.