Prove chromatic polynomial of n-cycle

Let graph $C_n$ denote a cycle with $n$ edges and $n$ vertices where $n$ is a nonnegative integer. Let $P(G, x)$ denote the number of proper colorings of some graph $G$ using $x$ colors.

Theorem: $P(C_n,x)=(x-1)^n+(-1)^n(x-1)$

By graph reduction,

$P(C_n,x)=$ $P(P_{n-1},x)-P(C_{n-1},x)=P(P_{n-1},x)-P(P_{n-2},x)+P(C_{n-2},x)$.

If I continue to expand, I can write the expression using only paths:

$P(C_n,x)=P(P_{n-1},x)-P(P_{n-2},x)+\dots+(-1)^{n+1}P(P_0,x))$

The number of proper colorings of a simple path is $x(x-1)^{n-1}$. So

$P(C_n,x)=x(x-1)^{(n-1)-1}-x(x-1)^{(n-2)-1}+\dots+(-1)^{n+1}x(x-1)^{-1}$.

Have I made any mistakes? Is it possible to prove the theorem using this method or should I be using induction?

Solution 1:

You made a mistake at the beginning. The reduction should be $$P(C_n,x)=P(P_n,x)-P(C_{n-1},x)$$ which holds for $n\ge2$. I don't know what $P_0$ means. We have: $$P(C_1,x)=0$$ $$P(C_2,x)=P(P_2,x)-P(C_1,x)=P(P_2,x)-0=P(P_2,x)$$ $$P(C_3,x)=P(P_3,x)-P(C_2,x)=P(P_3,x)-P(P_2,x)$$ $$P(C_4,x)=P(P_4,x)-P(P_3,x)+P(P_2,x)$$ $$P(C_5,x)=P(P_5,x)-P(P_4,x)+P(P_3,x)-P(P_2,x)$$ and in general (for $n\ge2)$ $$P(C_n,x)=P(P_n,x)-P(P_{n-1},x)+\cdots+(-1)^nP(P_2,x)$$ $$=x(x-1)^{n-1}-x(x-1)^{n-2}+\cdots+(-1)^nx(x-1)$$ $$=\frac{x(x-1)^{n-1}+(-1)^nx}{1+(x-1)^{-1}}$$ $$=(x-1)^n+(-1)^n(x-1).$$