Lesson 4

Now we are ready to prove the main result of this section.

Theorem. For any graph \(G\) on \(n\) vertices, the function \(P_{G}(x)\) is a polynomial of degree \(n\).

Proof. We will prove this by induction on the number of edges. The base case has already been checked above (for the empty graph). Now for the inductive step. The formula \[P_{G}(x)=P_{G \setminus e}(x)-P_{G / e}(x)\] allows us to express \(P_{G}(x)\) in terms of the same function for graphs with fewer edges. By the induction hypothesis, these two functions are polynomials, so their difference is also a polynomial.◼

This proof also implies various properties of the chromatic polynomial—for example, that the leading coefficient is one, and that the signs of its coefficients alternate.