Degree of chromatic polynomial We have graph with $n$ vertices. Chromatic number of this graph is $\chi(G)=3$.
What degree has a chromatic polynomial of this graph? I ended up with degree of size $n$, but I can not find proof for that.
 A: The degree of the chromatic polynomial is equal to the number of vertices. Here is a simple proof from first principles.
Let $G=(V,E)$ be a (simple finite) graph of order $n.$ For $x\in\mathbb N$ let $P(x)$ be the number of proper colorings $\varphi:V\to\{1,2,3,\dots,x\}.$ For $e=uv\in E,$ let $A_e$ be the number of maps $\varphi:V\to\{1,2,3,\dots,x\}$ such that $\varphi(u)=\varphi(v).$ Plainly,
$$P(x)=x^n-\left|\bigcup_{e\in E}A_e\right|.\tag1$$
Using the in-and-out formula (the so-called "Principle of Inclusion and Exclusion") we can rewrite this as
$$P(x)=x^n+\sum_{\emptyset\ne F\subseteq E}(-1)^{|F|}\left|\bigcap_{e\in F}A_e\right|=x^n+\sum_{\emptyset\ne F\subseteq E}(-1)^{|F|}|A_F|\tag2$$
where $A_F=\bigcap_{e\in F}A_e.$ But $|A_F|=x^{n(F)}$ where $n(F)$ is the number of connected components of the graph $(V,F),$ so we can rewrite this as
$$P(x)=x^n+\sum_{\emptyset\ne F\subseteq E}(-1)^{|F|}x^{n(F)}.\tag3$$
Since $n(F)\lt|V|=n$ when $F\ne\emptyset,$ this is a polynomial in $x$ of degree $n.$
A: The degree of the chromatic polynomial is equal to the number of vertices.
A proof of this should be in essentially every textbook that treats chromatic polynomials.
