stylistic:style_transfer, quality:correction
Deletion–contraction

The fact that the number of k -colorings is a polynomial in k follows from a recurrence relation called the deletion–contraction recurrence or Fundamental Reduction Theorem. It is based on edge contraction: for a pair of vertices u {\displaystyle u} and v {\displaystyle v} the graph G / u v {\displaystyle G/uv} is obtained by merging the two vertices and removing any edges between them. If u {\displaystyle u} and v {\displaystyle v} are adjacent in G, let G − u v {\displaystyle G-uv} denote the graph obtained by removing the edge u v {\displaystyle uv}.Then the numbers of k -colorings of these graphs satisfy:

Equivalently, if u {\displaystyle u} and v {\displaystyle v} are not adjacent in G and G + u v {\displaystyle G+uv} is the graph with the edge u v {\displaystyle uv} added, then

This follows from the observation that every k -coloring of G either gives different colors to u {\displaystyle u} and v {\displaystyle v}, or the same colors. In the first case this gives a (proper) k -coloring of G + u v {\displaystyle G+uv}, while in the second case it gives a coloring of G / u v {\displaystyle G/uv}.Conversely, every k -coloring of G can be uniquely obtained from a k -coloring of G + u v {\displaystyle G+uv} or G / u v {\displaystyle G/uv} (if u {\displaystyle u} and v {\displaystyle v} are not adjacent in G).

The chromatic polynomial can hence be recursively defined as

Since the number of k -colorings of the edgeless graph is indeed k n {\displaystyle k^{n}}, it follows by induction on the number of edges that for all G, the polynomial P (G, x) {\displaystyle P(G,x)} coincides with the number of k -colorings at every integer point x = k. In particular, the chromatic polynomial is the unique interpolating polynomial of degree at most n through the points

Tutte ’s curiosity about which other graph invariants satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the Tutte polynomial T G (x, y) {\displaystyle T_{G}(x,y)}.