###### Problem 243

In Chapter 2 we introduced the deletion-contraction recurrence for counting spanning trees of a graph. Figure out how the chromatic polynomial of a graph is related to those resulting from deletion of an edge \(e\) and from contraction of that same edge \(e\text{.}\) Try to find a recurrence like the one for counting spanning trees that expresses the chromatic polynomial of a graph in terms of the chromatic polynomials of \(G-e\) and \(G/e\) for an arbitrary edge \(e\text{.}\) Use this recurrence to give another proof that the number of ways to color a graph with \(x\) colors is a polynomial function of \(x\text{.}\)

One way to get a proper coloring of \(G-e\) is to start with a proper coloring of \(G\) and remove \(e\text{.}\) But there are other colorings of \(G\) that become proper when you remove \(e\text{.}\)