Let 
be an undirected graph, and let 
denote the cardinal number
of the set of externally active edges of a spanning tree 
of 
, 
denote the cardinal number
of the set of internally active edges of 
, and 
the number of spanning trees of 
whose internal activity is 
and external activity is 
. Then the Tutte polynomial, also known as the dichromate or
Tutte-Whitney polynomial, is defined by
 |
(1)
|
(Biggs 1993, p. 100).
An equivalent definition is given by
 |
(2)
|
where the sum is taken over all subsets 
of the edge set of a graph 
, 
is the number of connected components of the subgraph on
vertices induced by 
, 
is the vertex count of 
, and 
is the number of connected components of 
.
Several analogs of the Tutte polynomial have been considered for directed graphs, including the cover polynomial (Chung and Graham 1995), Gordon-Traldi
polynomials (Gordon and Traldi 1993), and three-variable 
-polynomial (Awan and Bernardi 2016; Chow 2016). However, with
the exceptions of the Gordon-Traldi polynomial 
and 
-polynomial, these are not proper generalizations of the Tutte
polynomial since they are not equivalent to the Tutte polynomial for the special
case of undirected graphs (Awan and Bernardi 2016).
The Tutte polynomial can be computed in the Wolfram Language using TuttePolynomial[g,
x, y
].
The Tutte polynomial is multiplicative over disjoint unions.
For an undirected graph on 
vertices with 
connected components, the Tutte polynomial is given by
 |
(3)
|
where 
is the rank polynomial (generalizing Biggs 1993,
p. 101). The Tutte polynomial is therefore a rather general two-variable graph
polynomial from which a number of other important one- and two-variable polynomials
can be computed.
For not-necessarily connected graphs, the Tutte polynomial 
is related the chromatic
polynomial 
,
flow polynomial 
, rank polynomial 
, and reliability
polynomial 
by
 |  |  |
(4)
|
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
where 
is the number of vertices in the graph, 
is the number of edges, and 
is the number of connected components.
The Tutte polynomial of the dual graph 
of a graph 
is given by
 |
(8)
|
i.e., by swapping the variables of the Tutte polynomial of the original graph. A special case of this identity relates the flow polynomial 
of a planar
graph 
to the chromatic polynomial of its dual
graph 
by
 |
(9)
|
The Tutte polynomial of a connected graph 
is also completely defined by the following two properties
(Biggs 1993, p. 103):
1. If 
is an edge of 
which is neither a loop nor an isthmus, then 
.
2. If 
is formed from a tree with 
edges by adding 
loops, then 
Closed forms for some special classes of graphs are summarized in the following table, where 
and 
.
The Tutte polynomial of the web graph was considered
by Biggs et al. (1972) and Brennan et al. (2013).
| graph |  |
book
graph  | ![((1+x+x^2)^n[x(y-1)-y]+y(x+x^2+y)^n)/(y-1)](/images/equations/TuttePolynomial/Inline65.svg) |
| centipede graph |  |
cycle graph  |  |
empty
graph  | 1 |
| forest |  |
| gear graph |  |
| helm graph | ![x^n{-1-x-y+xy+2^(-n)[(1-t+x+y)^n+(1+t+x+y)^n]}](/images/equations/TuttePolynomial/Inline72.svg) |
| ladder graph |  |
| ladder rung graph |  |
| pan graph | ![(x[x^n+x(y-1)-y])/(x-1)](/images/equations/TuttePolynomial/Inline75.svg) |
path graph  |  |
star
graph  |  |
sunlet graph  |  |
wheel graph  | ![xy-x-y-1+2^(1-n)[(x+y+1+t)^(n-1)+(x+y+1-t)^(n-1)]](/images/equations/TuttePolynomial/Inline83.svg) |
The following table summarizes the recurrence relations for Tutte polynomials for some simple classes of graphs.
An equation for the Tutte polynomial 
of the complete graph 
was found by Tutte (1954, 1967). In
particular, 
has exponential generating function
![sum_(n=1)^inftyT_(K_n)(x,y)(u^n)/(n!)=1/(x-1){[sum_(n=0)^inftyy^((n; 2))(y-1)^(-n)(u^n)/(n!)]^((x-1)(y-1))-1},](/images/equations/TuttePolynomial/NumberedEquation6.svg) |
(10)
|
(Gessel 1995, Gessel and Sagan 1996). This can be written more simply in terms of the coboundary polynomial
 |
(11)
|
where 
is the connected component count and 
is the vertex count of a
graph 
(Martin and Reiner 2005). In this form, the exponential generating function of 
is given by
 |
(12)
|
which can be converted to the corresponding Tutte polynomial using the above relationship and the substitution 
and 
.
The formula was rediscovered by Pak in the form of the following recurrence
 |
(13)
|
where 
.
A formula for the Tutte polynomial of a complete bipartite graph 
is given in terms of an bivariate exponential
generating function for the coboundary polynomial as
 |
(14)
|
by Martin and Reiner (2005).
Nonisomorphic graphs do not necessarily have distinct Tutte polynomials. de Mier and Noy (2004) call a graph that is determined by its Tutte polynomial a 
-unique graph and showed that wheel
graphs, ladder graphs, Möbius
ladders, complete multipartite graphs (with the exception of 
), and hypercube graphs
are 
-unique
graphs. Kuhl (2008) showed that the generalized
Petersen graphs 
and their line graphs 
are 
-unique.
The numbers of simple graphs on 
, 2, ... nodes that are not Tutte-unique for a given value
of 
are 0, 0, 0, 4, 15, 84, 548, 5629, ... (OEIS A243048),
while the corresponding numbers of Tutte-unique graphs are 1, 2, 4, 7, 19, 72, 496,
6717, ... (OEIS A243049). The following table
summarizes some small co-Tutte graphs.
 | Tutte polynomial | graphs |
| 4 |  |  , ladder rung graph  |
| 4 |  | claw
graph  ,
path graph  |
| 5 |  |  ,  |
| 5 |  |  ,
 ,
 |
| 5 |  | fork graph,
path graph  , star graph  |
| 5 |  | paw
graph  ,
 |
| 5 |  | bull
graph, cricket graph,  -tadpole graph |
| 5 |  | dart graph, kite graph |
