Tutte Polynomial - Definitions

Definitions

For an undirected graph one may define the Tutte polynomial as

Here, denotes the number of connected components of the graph . In this definition it is clear that is well-defined and a polynomial in and . The same definition can be given using slightly different notation by letting denote the rank of the graph . Then the Whitney rank generating function is defined as

the two functions are equivalent under a simple change of variables: . Tutte’s dichromatic polynomial is the result of another simple transformation:

Tutte’s original definition of is equivalent but less easily stated. For connected we set

where denotes the number of spanning trees of “internal activity and external activity .”

A third definition uses a deletion–contraction recurrence. The edge contraction of graph is the graph obtained by merging the vertices and and removing the edge . We write for the graph where the edge is merely removed. Then the Tutte polynomial is defined by the recurrence relation

if is neither a loop nor a bridge

with base case

if contains bridges and loops and no other edges.

Especially, if contains no edges.

The random cluster model from statistical mechanics due to Fortuin & Kasteleyn (1972) provides yet another equivalent definition. The polynomial

is equivalent to under the transformation