# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## Category Archives: graphs

## 68: The Tutte Polynomial

December 19, 2016

Posted 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

.

Some properties:

- 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.

## Recent Comments