Suppose and is a proper -colouring of . Must there be a path in with for each ?
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...)
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.