Editing Matroid (section)

===Tutte polynomial===
The ''[[Tutte polynomial]]'' of a matroid, <math> T_M(x, y)</math>, generalizes the characteristic polynomial to two variables. This gives it more combinatorial interpretations, and also gives it the duality property
:<math> T_{M^*}(x,y) = T_M(y,x)</math>,
which implies a number of dualities between properties of <math> M </math> and properties of <math> M^*</math>. One definition of the Tutte polynomial is
:<math> T_M(x,y) = \sum_{S \subseteq E} (x-1)^{ r(M) - r(S) }\ (y-1)^{ |S| - r(S) }</math>.

This expresses the Tutte polynomial as an evaluation of the ''co-rank-nullity'' or ''rank generating polynomial'',<ref name=Wh87126>{{harvp|White|1987|p=126}}</ref>
:<math> R_M(u,v) = \sum_{S\subseteq E} u^{r(M)-r(S)}v^{|S| - r(S)}</math>.
From this definition it is easy to see that the characteristic polynomial is, up to a simple factor, an evaluation of <math> T_M</math>, specifically, 
:<math> p_M(\lambda) = (-1)^{r(M)} T_M(1-\lambda,0)</math>.

Another definition is in terms of internal and external activities and a sum over bases, reflecting the fact that <math> T(1,1) </math> is the number of bases.<ref name=Wh92188>{{harvp|White|1992b|p=188}}</ref> This, which sums over fewer subsets but has more complicated terms, was Tutte's original definition.

There is a further definition in terms of recursion by deletion and contraction.<ref name=Wh86260>{{harvp|White|1986|p=260}}</ref> The deletion-contraction identity is
:<math> F(M) = F( M - e ) + F( M / e ) </math>
when <math> e </math> is neither a loop nor a coloop.
An invariant of matroids (i.e., a function that takes the same value on isomorphic matroids) satisfying this recursion and the multiplicative condition
:<math> F(M \oplus M') = F(M) F(M')</math>
is said to be a ''Tutte-Grothendieck invariant''.<ref name=Wh87126/> The Tutte polynomial is the most general such invariant; that is, the Tutte polynomial is a Tutte-Grothendieck invariant and every such invariant is an evaluation of the Tutte polynomial.<ref name=Wh87127>{{harvp|White|1987|p=127}}</ref>

The [[Tutte polynomial]] <math> T_G </math> of a graph is the Tutte polynomial <math> T_{ M(G) } </math> of its cycle matroid.