Proposition 1 Use $m(m \geqslant 2)$ different colors to color $n(n \geqslant 2)$ interconnected regions $A_{1}, A_{2}, \cdots, A_{n}$ in Figure 1, and any two adjacent regions must be colored differently. Then the number of different coloring schemes is
$$
a_{n}=(-1)^{n}(m-1)+(m-1)^{n} \text {. }
$$
Proof: As shown in Figure 1, let the number of valid coloring schemes be $a_{n}$. Then region $A_{1}$ has $m$ coloring methods, and regions $A_{2}, A_{3}, \cdots, A_{n}$ each have $m-1$ coloring methods. This includes two cases: if region $A_{n}$ and $A_{1}$ are colored the same, then merging $A_{n}$ and $A_{1}$ into one region results in $n-1$ regions, with $a_{n-1}$ valid coloring schemes; if region $A_{n}$ and $A_{1}$ are colored differently, then it is valid, with $a_{n}$ coloring methods. Therefore, we have
$$
a_{n} + a_{n-1} = m(m-1)^{n-1}.
$$

Multiplying both sides by $(-1)^{n}$, we get
$$
\begin{array}{l}
(-1)^{n} a_{n} - (-1)^{n-1} a_{n-1} \\
= -m(1-m)^{n-1}.
\end{array}
$$

Summing both sides, we get
$$
\begin{array}{l}
\sum_{k=3}^{n}\left[(-1)^{k} a_{k} - (-1)^{k-1} a_{k-1}\right] \\
= -m \sum_{k=3}^{n}(1-m)^{k-1}. \\
\text{Thus, } (-1)^{n} a_{n} - a_{2} \\
= -(1-m)^{2} + (1-m)^{n}.
\end{array}
$$

Since $a_{2} = m(m-1)$, we have
$$
\begin{array}{l}
(-1)^{n} a_{n} \\
= (1-m)^{n} + m(m-1) - (1-m)^{2} \\
= (1-m)^{n} + (m-1).
\end{array}
$$

Therefore, $a_{n} = (-1)^{n}(m-1) + (m-1)^{n}$.