Editing Chromatic polynomial (section)

===Deletion–contraction===
{{Main|Deletion–contraction formula}}
The fact that the number of ''k''-colorings is a polynomial in ''k'' follows from a recurrence relation called the '''[[Deletion–contraction formula|deletion–contraction recurrence]]''' or '''Fundamental Reduction Theorem'''.<ref>{{harvtxt|Dong|Koh|Teo|2005}}</ref> It is based on [[edge contraction]]: for a  pair of vertices <math>u</math> and <math>v</math> the graph <math>G/uv</math> is obtained by merging the two vertices and removing any edges between them. 
If <math>u</math> and <math>v</math> are adjacent in ''G'', let <math>G-uv</math> denote the graph obtained by removing the edge <math>uv</math>.
Then the numbers of ''k''-colorings of these graphs satisfy:
:<math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>
Equivalently, if <math>u</math> and <math>v</math> are not adjacent in ''G'' and <math>G+uv</math> is the graph with the edge <math>uv</math> added, then
:<math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>
This follows from the observation that every ''k''-coloring of ''G'' either gives different colors to <math>u</math> and <math>v</math>, or the same colors. In the first case this gives a (proper) ''k''-coloring of <math>G+uv</math>, while in the second case it gives a coloring of <math>G/uv</math>.
Conversely, every ''k''-coloring of ''G'' can be uniquely obtained from a ''k''-coloring of <math>G+uv</math> or <math>G/uv</math> (if <math>u</math> and <math>v</math> are not adjacent in ''G'').

The chromatic polynomial can hence be recursively defined as 
:<math>P(G,x)=x^n</math> for the edgeless graph on ''n'' vertices, and 
:<math>P(G,x)=P(G-uv, x)- P(G/uv,x)</math> for a graph ''G'' with an edge <math>uv</math> (arbitrarily chosen).
Since the number of ''k''-colorings of the edgeless graph is indeed <math>k^n</math>, it follows by induction on the number of edges that for all ''G'', the polynomial <math>P(G,x)</math> coincides with the number of ''k''-colorings at every integer point ''x''&nbsp;=&nbsp;''k''. In particular, the chromatic polynomial is the unique [[interpolating polynomial]] of degree at most ''n'' through the points
:<math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \ldots, (n, P(G, n)) \right \}.</math>

[[Tutte]]’s curiosity about which other [[graph invariant]]s satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the [[Tutte polynomial]] <math>T_G(x,y)</math>.