Lesson 1

For a graph \(G\), define the function \(P_{G} \colon \mathbb{Z}_{\ge 0}\to \mathbb{Z}_{\ge 0}\) as follows: \[P_{G}(x)=\text{number of proper \(x\)-colorings of \(G\)}\ .\] It turns out that for each graph \(G\), this function is a polynomial. We will prove this below.