Some of the things I've learned every day since Oct 10, 2016
68: The Tutte Polynomial
December 19, 2016Posted by on
In graph theory, the Tutte polynomial of a graph is a 2-variable polynomial which is well-defined for any undirected graph and contains information about that graph.
Let be an undirected graph, and let denote the number of connected components in , where . Then the Tutte polynomial is defined as
- Isomorphic graphs have the same Tutte polynomial, but the reverse is not the case
- Along , it specializes to the Jones polynomial of an associated alternating knot
- is the number of forests of
- If is connected, counts the number of spanning trees.
There are too many to list, but there are many other constraints one can place onto and get various kinds of information about . It enjoys a wide range of applications, from statistical physics to theoretical computer science.