The Tutte polynomial of a matroid is a polynomial $T\left(x\,y\right)$ in two variables. It is a matroid invariant (two isomorphic matroids have the same Tutte polynomial) which respects the operations of deletion and contraction. Specifically, for any element $e$ in the ground set of a matroid $M$ which is neither a loop (contained in no basis) nor coloop (contained in every basis) we have the following recursion:

where $T_N\left(x\,y\right)$ is the Tutte polynomial of $N$ and we write $M\setminus \left\{e\right\}$ for the deletion of $e$ from $M$ and $M/\left\{e\right\}$ for the contraction from $M$ by $e$.

The Tutte polynomial of the dual of the matroid $M$ is $T\left(y\,x\right)$.

The Tutte polynomial has several alternative definitions. For example, there is one in terms of basis "activities".

The evaluation $T\left(1\,1\right)$ gives the number of bases of a matroid.

The characteristic polynomial of a matroid is the evaluation $T\left(1-k\,0\right)$, multiplied by $\mathrm{-1}$ if the rank of the matroid is odd.

$\mathrm{with}\left(\mathrm{Matroids}\right)\:$

$\mathrm{with}\left(\mathrm{ExampleMatroids}\right)\:$

$M≔\mathrm{Fano}\left(\right)$

$M≔⟨\mathrm{a\; matroi\ⅆ\; on\; 7\; \ⅇl\ⅇm\ⅇnts\; with\; 14\; circuits}⟩$

$T≔\mathrm{TuttePolynomial}\left(M\,x\,y\right)$

$T≔y^4+x^3+3y^3+4x^2+7yx+6y^2+3x+3y$

$\mathrm{eval}\left(T\,\left[x=1\,y=1\right]\right)$

$28$

$\mathrm{TuttePolynomial}\left(M\,1\,1\right)$

$28$

James G. Oxley. Matroid Theory (Oxford Graduate Texts in Mathematics). New York: Oxford University Press. 2006.