Tutte polynomial

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a <a href="/facts/Graph_polynomial/KxhTDR0l">graph polynomial</a>. It is a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> in two variables which plays an important role in <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>. It is defined for every <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 and contains information about how the graph is connected. It is denoted by 
 
 
 
 
 T
 
 G
 
 
 
 
 {\displaystyle T_{G}}
 
.
The importance of this polynomial stems from the information it contains about 
 
 
 
 G
 
 
 {\displaystyle G}
 
. Though originally studied in <a href="/facts/Algebraic_graph_theory/5HNDPx8g">algebraic graph theory</a> as a generalization of counting problems related to <a href="/facts/Graph_coloring/J6HoBfP0">graph coloring</a> and <a href="/facts/Nowhere-zero_flow/NYW9vQhk">nowhere-zero flow</a>, it contains several famous other specializations from other sciences such as the <a href="/facts/Jones_polynomial/c73vElt9">Jones polynomial</a> from <a href="/facts/Knot_theory/mb7rtqVP">knot theory</a> and the <a href="/facts/Partition_function_(statistical_mechanics)/q65sJrrn">partition functions</a> of the <a href="/facts/Potts_model/JlSQMYH1">Potts model</a> from <a href="/facts/Statistical_physics/SnlJE78a">statistical physics</a>. It is also the source of several central <a href="/facts/Computational_problem/jQ7bYUVh">computational problems</a> in <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>.
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 <a href="/facts/Random_cluster_model/gTUa7XtJ">random cluster model</a> under simple transformations. It is essentially a <a href="/facts/Generating_function/K7UVjnjL">generating function</a> for the number of edge sets of a given size and connected components, with immediate generalizations to <a href="/facts/Matroid/5bLcGlRF">matroids</a>. It is also the most general <a href="/facts/Graph_invariant/bjuIvgb1">graph invariant</a> that can be defined by a <a href="/facts/Deletion%25E2%2580%2593contraction_formula/H5aXmbrh">deletion–contraction recurrence</a>. Several textbooks about graph theory and matroid theory devote entire chapters to it.

Tutte polynomial open-in-new

Tutte polynomial