Informal: I want to show that a q-coloring of graph $G$ is ergodic (i.e. strongly connected and aperiodic)
Formally: For a given graph $G(V,E)$ where $|V|=n$ with maximum degree $\Delta\geq1$. Also, let $q=4\Delta$.
Denote a q-coloring of $G$ as a function $c:V\rightarrow[q]$ s.t for every edge $(u,v)\in E \mid c(u)\neq c(v)$.
Define $\Omega=${The state space of all the legal q-coloring of $G$} and consider the following Markov chain:
Say the current state is $X_0 = c\in \Omega$ Sample $(v, i)\in V \times [q]$ uniformly at random and independently from previous choices.
Define $\hat{c}:V\rightarrow[q]$ by setting $\hat{c}=c(u)\quad \forall\, u\neq v$ $\hat{c}(v)=i$.$\quad$ So a step in the MC defined as: $$ x_{t+1} = \left. \begin{cases} \hat{c}, & \text{if } c\in \Omega \\ x_{t}, & \text{else } \end{cases} \right\} $$ In words: If $\hat{c}$ is a valid coloring, (which happens if color $i$ isn't used by coloring $c$ on any neighbor of $v$) set $X_{t+1} = \hat{c}$. Otherwise $X_{t+1} = c$.
How can I show (formally) that the MC is ergodic?
We first show that the Markov chain is strongly connected. Take two colorings $c$ and $c'$ of $G$. For ease, label the vertices of $G$ as $[n]$. Call a vertex "on" if its color matches that prescribed by $c'$ and "off" otherwise. We will start at $c$ and change colors as allowed by the Markov chain until all vertices are "on". Suppose that we have changed the coloring so far so that $1,2,\dots,j$ are "on" and $j+1$ is off (with $j$ possibly equal to $0$). If no neighbor of $j+1$ has color $c'(j+1)$, then we can change the color of $j+1$ to $c'(j+1)$. Otherwise, say $m_1,\dots,m_k$ are the neighbors of $j+1$ that have color $c'(j+1)$. Note that each $m_i$ is at least $j+2$, since $c'$ is a valid coloring and vertices $1$ through $j$ are "on". First, since $m_1$ has at most $\Delta$ neighbors and there are $4\Delta$ colors, we may change the color of $m_1$ to anything legal that is not $c'(j+1)$. Then, by the same reasoning, we can change the color of $m_2$. Etc. until $m_k$. (Note that we couldn't change the colors of $m_1,\dots,m_k$ simultaneously, since the $m_i$'s could be connected to one another). Now, we may legally change the color of $j+1$ to $c'(j+1)$. Therefore, we can color all vertices to be "on" and thus get to $c'$.
Now we show that the Markov chain is aperiodic. Take $c \in \Omega$. There is clearly a path of length $2$ from $c$ to itself: merely change a color of a vertex to a color not had by a neighbor (which is possible since $4\Delta > \Delta$) and then back to the original color. Similarly, a path of length $3$ from $c$ to itself is possible: change the color twice to two distinct colors, neither of which is the original color, and then change the color back to the original color. Therefore, any color has period $1$, and thus $\Omega$ is aperiodic.