How much options are there to color a circular graph with $10,000$ nodes with $2023$ colors? How much options are there to color a circular graph with $10,000$ nodes with $2023$ colors ?
Let $ c_n $ the undirected simple circular graph on $n$ nodes.
$E=\big\{\{1,2\},\ldots,\{n-1,n\},\{n,1\}\big\}.$
How many options there are to paint $c_n$ if $n= 1000$ and we demand that each adjacent node has different colour?
I came to an estimation by using inclusion-exclusion principle and the binomial theorem, yet I am not certain this is right...
$\displaystyle\sum_{k=0}^{10,000}\binom{10000}{k}(2023)^{10,000-k}\cdot(-1)^{k}=2022^{k}$
as also noted, the nodes are numbered so rotation and reflections do not apply here.
 A: Hint: The number of ways to colour the circular graph on $n$ nodes with $c$ colours should be $\text{trace}(A^{n})$ where $A$ is the $c \times c$ matrix with all diagonal entries $0$ and all off-diagonal entries $1$.
A: Let $c_{n,k}$ be the number of proper colorings of a labeled circular graph with $n$ nodes using $k$ colors (i.e., colorings where no two adjacent nodes have the same color).  You can color the first node in $k$ ways; each subsequent node can be colored in $k-1$ ways; and the final node needs to be colored differently than the first.  But the number of ways to color the graph where the final node is the same color as the first is just $c_{n-1,k}$.  So $$c_{n,k}=k\cdot(k-1)^{n-1}-c_{n-1,k},$$
where the recursion terminates with $c_{1,k}=0$.  Expanding out, you find that
$$
\begin{eqnarray}
c_{n,k} &=& k\cdot(k-1)^{n-1}\cdot\left(1-\frac{1}{k-1}+\frac{1}{(k-1)^2}-\ldots \pm \frac{1}{(k-1)^{n-2}}\right) \\ &=& (k-1)^n \pm (k-1),
\end{eqnarray}
$$
where the sign is $+$ for even $n$ and $-$ for odd $n$.
