What is an example of a Hamiltonian graph $G=(V,E)$ such that there is one path visiting all vertices that is *not* chromatic (definition see below)?




---


Let $G= (V,E)$ be a simple undirected graph on $n\geq 1$ vertices, and let $b:[n]\to V$ be a bijection. We assign to $b$ the greedy coloring $c\_b$ constructed by traversing the graph in the order $b$. Formally, with recursive definition of $c\_b:[n] \to [n]$:


* $c\_b(1) = 1$;
* if $k\in[n]$ and $k>1$ let 
$$c\_b(k) = \min\:\big(\mathbb{N}\setminus\{c\_b(j): j \in [k-1]\land \{b(j),b(k)\}\in E\}\big).$$


We call $b$ *chromatic* if $\text{im}(c\_b) = [\chi(G)]$. For every graph there is a chromatic bijection (see [here](https://en.wikipedia.org/wiki/Greedy_coloring#Optimal_ordering)). A *chromatic path* is a chromatic bijection that is also a [path](https://en.wikipedia.org/wiki/Path_(graph_theory)).



Non-chromatic paths in Hamiltonian graphs
**Counterexample.** Let $G$ be the graph with vertices $v\_1,v\_2,v\_3,v\_4,v\_5,v\_6$ and edges $v\_1v\_2,v\_2v\_3,v\_3v\_4,v\_4v\_5,v\_5v\_6,v\_6v\_1,v\_1v\_5,v\_4v\_6.$


The graph $G$ is Hamiltonian, since $v\_1,v\_2,v\_3,v\_4,v\_5,v\_6,v\_1$ is a Hamiltonian cycle.


The graph $G$ is $3$-chromatic; for a proper coloring, we may color $v\_1$ and $v\_4$ red, $v\_2$ and $v\_5$ white, $v\_3$ and $v\_6$ blue.


The path $v\_1,v\_2,v\_3,v\_4,v\_5,v\_6$ is not chromatic.


