How to prove $G$ is connected?

Question

Problem Description:

Given a tree $T$, we construct a graph $G$ where:

• The vertices of $G$ are the proper 3-colorings of $T$.
• An edge exists between two vertices in $G$ if the corresponding colorings differ at exactly one vertex in $T$.

The goal is to prove that the graph $G$ is connected.

My Current Proof Outline:

To prove the connectivity of $G$, we need to show that for any two proper 3-colorings $C_1 $ and $C_2$ of $T$, there exists a sequence of proper colorings starting from $C_1$ and ending at $C_2$ such that each consecutive pair of colorings in the sequence differ at exactly one vertex and are proper 3-colorings.

Definition of Proper 3-Coloring:

• A proper 3-coloring means that adjacent vertices in $T$ have different colors.

Question:

How can we rigorously prove this process, ensuring that every proper 3-coloring can indeed be reached from any other through a series of colorings that differ by only one vertex of $T$?

Is there a more systematic approach to prove the connectivity of $ G $? Any detailed insights or alternative methods would be greatly appreciated.

additional perscription:

This question is exercise 1.5 of Markov Chains and Mixing Times,

Answer 1

I will only give a sketch of the argument. We will use induction on the number $n$ of vertices of $T$. When $n = 1$ the claim is clear. Suppose then that it holds for trees of size $n$. Let $T$ be a tree of size $n+1$. Pick a leaf $v$ of $T$. (This is where we really use the fact that $T$ is a tree.) Let $C_1,C_2$ be proper $3$-colorings of $T$. Their restrictions to $T - \{v\}$ are also proper $3$-colorings and hence by induction we get that there exists a path between them. Because $v$ was a leaf, this path also induces a path between $C_1$ and $C_2$. (This uses the fact that $v$ is a leaf, because we can modify the color of $v$ when it is necessary.)