Maths Project Repository Database

The Tutte polynomial $T(G;x,y)$ is a two-variable polynomial associated with an undirected graph G. Evaluating the polynomial at various points provides a wealth of information about G. For example, $T(G;1,1)$ is the number of spanning trees in G and $T(G,-2,0)$ is the number of 3-colourings of G. The project would need to survey different definitions of the Tutte polynomial (in terms of contraction/deletion, and in terms of a rank function), and survey (with proofs) several of the combinatorial interpretations of the polynomial.