# Today I Learned

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

## 68: The Tutte Polynomial

In graph theory, the Tutte polynomial $T_G$ of a graph $G$ is a 2-variable polynomial which is well-defined for any undirected graph and contains information about that graph.

Let $G = (V, E)$ be an undirected graph, and let $k(A)$ denote the number of connected components in $G' = (V, A)$, where $A \subseteq E$. Then the Tutte polynomial is defined as

$T_G (x, y) = \sum _{A \subseteq E} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V|}$.

Some properties:

• Isomorphic graphs have the same Tutte polynomial, but the reverse is not the case
• Along $xy = 1$, it specializes to the Jones polynomial of an associated alternating knot
• $T_G (2, 1)$ is the number of forests of $G$
• If $G$ is connected, $T_G (1, 1)$ counts the number of spanning trees.

There are too many to list, but there are many other constraints one can place onto $T_G$ and get various kinds of information about $G$. It enjoys a wide range of applications, from statistical physics to theoretical computer science.