The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph and contains information about how the graph is connected. It is denoted by .
The importance of this polynomial stems from the information it contains about . Though originally studied in algebraic graph theory as a generalization of counting problems related to graph coloring and nowhere-zero flow, it contains several famous other specializations from other sciences such as the Jones polynomial from knot theory and the partition functions of the Potts model from statistical physics. It is also the source of several central computational problems in theoretical computer science.
The Tutte polynomial has several equivalent definitions. It is essentially equivalent to Whitney’s rank polynomial, Tutte’s own dichromatic polynomial and Fortuin–Kasteleyn’s random cluster model under simple transformations. It is essentially a generating function for the number of edge sets of a given size and number of connected components, with immediate generalizations to matroids. It is also the most general graph invariant that can be defined by a deletion–contraction recurrence. Several textbooks about graph theory and matroid theory devote entire chapters to it....
Definitions Definition. For an undirected graph one may define the Tutte polynomial as
where 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 . To define these notions, we assume that the set of edges of the graph is totally ordered, , and suppose given a spanning tree . An edge is said to be internally active if it is the smallest edge of its fundamental cutset. Dually, an edge is said to be externally active if it is the smallest edge of its fundamental cycle. The internal activity and external activity of a spanning tree are the numbers of internal and external edges, respectively. Although the specific set of internal and external edges depends on the choice of total order on the edges, the total number of spanning trees of internal activity and external activity is independent of the order chosen. Moreover, this definition of extends to not-necessarily-connected graphs if we take to be the number of spanning forests of internal activity and external activity , where a "spanning forest" is meant in the sense of a collection of spanning trees, one for each connected component of .
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. In particular, if contains no edges.
The random cluster model from statistical mechanics due to provides yet another equivalent definition.. The partition sum
is equivalent to under the transformation.
Properties The Tutte polynomial factors into connected components. If is the union of disjoint graphs and then
Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every forest on edges is .
If is planar and denotes its dual graph then
In particular, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.
Examples
The figures show two ways of calculating the Tutte polynomial of a small graph with four nodes and four edges, either via the deletion–contraction formula or by enumeration of spanning trees.
Tutte polynomials are often given in tabular form by listing the coefficients of in row and column . For example, the Tutte polynomial of the Petersen graph,
is given by the following table.
0 36 84 75 35 9 1 36 168 171 65 10 120 240 105 15180 170 30170 70 114 12 56 21 6 1
Other example, the Tutte polynomial of the octahedron graph is given by
History The polynomial was introduced by W. T. Tutte in his 1954 paper, "A contribution to the theory of chromatic polynomials" . Tutte’s interest in the deletion–contraction formula started already in his undergraduate days at Trinity College, Cambridge, originally motivated by perfect rectangles and spanning trees. As he wrote in a later account, he often applied the formula in his research and “wondered if there were other interesting functions of graphs, invariant under isomorphism, with similar recursion formulae.”. R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more, which he wrote about in a paper published in 1947, "A ring in graph theory". His original terminology for graph invariants that satisfy the deletion–contraction recursion was W-function, and V-function if multiplicative over components. Tutte writes in the later account, “Playing with my W-functions I obtained a two-variable polynomial from which either the chromatic polynomial or the flow-polynomial could be obtained by setting one of the variables equal to zero, and adjusting signs.” Tutte called this function the dichromate, as he saw it as a generalization of the chromatic polynomial to two variables, but it is usually referred to as the Tutte polynomial. In Tutte’s words, “This may be unfair to Hassler Whitney who knew and used analogous coefficients without bothering to affix them to two variables.” (There is “notable confusion” about the terms dichromate and dichromatic polynomial, introduced by Tutte in the earlier 1947 paper, the two differing only slightly by a change of variables.) The generalisation of the Tutte polynomial to matroids was first published by Crapo, though it appears already in Tutte’s thesis..
Independently of the work in algebraic graph theory, Potts began studying the partition function of certain models in statistical mechanics in 1952. The work by Fortuin and Kasteleyn. on the random cluster model, a generalisation of the Potts model, provided a unifying expression that showed the relation to the Tutte polynomial.
Specialisations Evaluating the Tutte polynomial at various points and lines of the -plane recovers quantities that have been studied in their own right in diverse fields of mathematics and physics, and part of the appeal of the Tutte polynomial thus comes from the unifying framework it provides for analysing these quantities. Here we list various polynomials that can be recovered as specializations of the Tutte polynomial, up to a factor that depends only on the number of components, rank, and/or nullity of a graph.These factors can also be incorporated directly into a more general, "universal" form of the Tutte polynomial: see section X.2 of .
Chromatic polynomial
The chromatic polynomial can be recovered from the Tutte polynomial by evaluating at ,
where denotes the number of connected components of G.
For integer λ the value of chromatic polynomial equals the number of vertex colourings of G using a set of λ colours. It is clear that does not depend on the set of colours. What is less clear is that it is the evaluation at λ of a polynomial with integer coefficients. To see this, we observe: If G has n vertices and no edges, then . If G contains a loop (a single edge connecting a vertex to itself), then . If e is an edge which is not a loop, then
The three conditions above enable us to calculate , by applying a sequence of edge deletions and contractions; but they give no guarantee that a different sequence of deletions and contractions will lead to the same value. The guarantee comes from the fact that counts something, independently of the recurrence. In particular,
gives the number of acyclic orientations.
Jones polynomial
Along the hyperbola , the Tutte polynomial of a planar graph specialises to the Jones polynomial of an associated alternating knot obtained via the medial graph construction. Louis Kauffman has proposed a generalization of the Tutte polynomial for signed graphs, which yields by the medial construction a knot polynomial that specializes to the Jones polynomial as well as to the Kauffman bracket polynomial.
Individual points
(2, 1) counts the number of forests, i.e., the number of acyclic edge subsets.
(1, 1) counts the number of spanning forests (edge subsets without cycles and the same number of connected components as G). If the graph is connected, counts the number of spanning trees.
(1, 2) counts the number of spanning subgraphs (edge subsets with the same number of connected components as G).
(2, 0) counts the number of acyclic orientations of G..
(0, 2) counts the number of strongly connected orientations of G..
(2, 2) is the number where is the number of edges of graph G.
(0, −2) If G is a 4-regular graph, then
counts the number of Eulerian orientations of G. Here is the number of connected components of G.
(3, 3) If G is the m × n grid graph, then counts the number of ways to tile a rectangle of width 4m and height 4n with T-tetrominoes..See for combinatorial interpretations of many other points.
If G is a planar graph, then equals the sum over weighted Eulerian orientations in a medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation (that is, the number of vertices with incident edges cyclicly ordered "in, out, in out")..
Potts and Ising models
Define the hyperbola in the xy−plane:
the Tutte polynomial evaluated at the hyperbola determines the partition function, of the Ising model studied in statistical physics. Specifically, along the hyperbola the two are related by the equation:.
In particular,
for all complex α.
More generally, if for any positive integer q, we define the hyperbola:
then the Tutte polynomial determines the partition function of the q-state Potts model. Various physical quantities analysed in the framework of the Potts model translate to specific parts of the .
+ Correspondences between the Potts model and the Tutte plane . Potts model Tutte polynomial Ferromagnetic Positive branch of Antiferromagnetic Negative branch of with High temperature Asymptote of to Low temperature ferromagnetic Positive branch of asymptotic to Zero temperature antiferromagnetic Graph q-colouring, i.e.,
Flow polynomial
The flow polynomial studied in combinatorics can be recovered from the Tutte polynomial by evaluating at . For a connected and undirected graph G and integer k, a nowhere-zero k-flow is an assignment of “flow” values to the edges of an arbitrary orientation of G such that the total flow entering and leaving each vertex is congruent modulo k. The flow polynomial denotes the number of nowhere-zero k-flows. This value is intimately connected with the chromatic polynomial, in fact, if G is a planar graph, the chromatic polynomial of G is equivalent to the flow polynomial of its dual graph in the sense that
Theorem (Tutte).
The connection to the Tutte polynomial is given by:
Reliability polynomial