Given a graph $G$, we can view each proper vertex-coloring of $G$, i.e., two adjacent vertices of $G$ receive different colors, as a state. And two states are adjacent if the two colorings only differ at one vertex.
If it is allowed to use at most $2\Delta+1$ colors for the proper coloring, where $\Delta$ is the maximum degree of $G$. I am wondering how to prove the state space is connected? I.e., given any two proper coloings of $G$, each time we are allowed to modify the color of one vertex to get a proper coloring, so that we can go from one proper coloring to the other?
If $2\Delta+1$ is not enough, what's about $3\Delta+1$?