the definition in mathworld.wolfram The chromatic polynomial P(G,x) is the unique monic n-degree polynomial such that P(G,k) = the number of k colorings of G, for k = 0,1,...,n. where colorings are counted as distinct even if they differ only permutation of colors. (According to Lagrange interpolation, it is unique and well-defined.)
In fact, evaluating P(G,x) at k > n still gives the number of k colorings.
My question is: how to prove this fact for k > n?
Thanks in advance for any possible help
Consider a graph $G=(V,E)$. Suppose $E=\{e_1,\dots,e_m\}$ where $e_i=u_iv_i$. For $I\subseteq[m]=\{1,\dots,m\}$, let $c(I)$ be the number of connected components in the spanning subgraph of $G$ with edge set $\{e_i:i\in I\}$.
Instead of defining $P(G,x)$ by Lagrange interpolation, let's define $P(G,k)$ (for all integers $k\ge0$) as the number of proper colorings $f:V\to[k]=\{1,\dots,k\}$, and let's prove that $P(G,k)$ is a polynomial in $k$ of degree $|V|$.
Consider a fixed integer $k\ge0$. Let $F$ be the set of all maps $f:V\to[k]$. For $i\in[m]$ let $F_i=\{f\in F:f(u_i)=f(v_i)\}$. Then, by the in-and-out formula, $$P(G,k)=|F|-\left|\bigcup_{i=1}^mF_i\right|=|F|+\sum_{\emptyset\ne I\subseteq[m]}(-1)^{|I|}\left|\bigcap_{i\in I}F_i\right|=k^{|V|}+\sum_{\emptyset\ne I\subseteq[m]}(-1)^{|I|}k^{c(I)}$$ which is a monic polynomial in $k$ of degree $|V|$.