Let $G$ be a graph (in the sense of graph theory) whose set $V$ of vertices is finite and nonempty, and which has no loops or multiple edges. For any natural number $x$, let $\chi(G,x)$, or just $\chi(x)$, denote the number of $x$-colorations of $G$, i.e. the number of mappings $f\colon V\to\{1,2,\ldots,x\}$ such that $f(a)\neq f(b)$ for any pair $(a,b)$ of adjacent vertices. Let us prove that $\chi$ (which is called the chromatic polynomial of the graph $G$) is a polynomial function in $x$ with coefficients in $\mathbb{Z}$. Write $E$ for the set of edges in $G$. If $|E|$=0, then trivially $\chi(x)=x^{{|V|}}$ (where $|\cdot|$ denotes the number of elements of a finite set). If not, then we choose an edge $e$ and construct two graphs having fewer edges than $G$: $H$ is obtained from $G$ by contracting the edge $e$, and $K$ is obtained from $G$ by omitting the edge $e$. We have

for all $x\in\mathbb{N}$, because the polynomial $\chi(K,x)$ is the number of colorations of the vertices of $G$ which might or might not be valid for the edge $e$, while $\chi(H,x)$ is the number which are not valid. By induction on $|E|$, (1) shows that $\chi(G,x)$ is a polynomial over $\mathbb{Z}$.

By refining the argument a little, one can show

for some nonzero integer $s$, where $k$ is the number of connected components of $G$, and the coefficients alternate in sign.

With the help of the Möbius-Rota inversion formula (see Moebius Inversion), or directly by induction, one can prove

where the sum is over all subsets $F$ of $E$, and $r(F)$ denotes the rank of $F$ in $G$, i.e. the number of elements of any maximal cycle-free subset of $F$. (Alternatively, the sum may be taken only over subsets $F$ such that $F$ is equal to the span of $F$; all other summands cancel out in pairs.)

The chromatic number of $G$ is the smallest $x>0$ such that $\chi(G,x)>0$ or, equivalently, such that $\chi(G,x)\neq 0$.

The Tutte polynomial of a graph, or more generally of a matroid $(E,r)$, is this function of two variables:

Compared to the chromatic polynomial, the Tutte contains more information about the matroid. Still, two or more nonisomorphic matroids may have the same Tutte polynomial.