# Determinantal formulae for Tutte polynomial

Let $G$ be a connected undirected graph. Then the number $ST(G)$ of spanning trees in $G$ equals the following specific value of the Tutte polynomial of $G$: $ST(G)=T_G(1,1)$.

On the other hand, Kirchhoff's matrix tree theorem expresses $ST(G)$ as a principal minor of Laplacian of $G$.

The question is wether the whole Tutte polynomial or at least some other values can be expressed as determinants. If in general they can't, I wonder what is behind this phenomenon.

• Determinants of what exactly? Since the Tutte polynomial is NP-hard to compute, we will need a large or complicated matrix. – Chris Godsil Jun 10 '15 at 0:26
• @ChrisGodsil I suppose that it may be related. Wiki page on Tutte polynomial lists several cases when it may be computed in polynomial time: hyperbola $(x-1)(y-1)=1$ and several isolated points, journals.cambridge.org/action/… Maybe, these are the points in which some formula appears to be determinantal? – Fedor Petrov Jun 10 '15 at 0:47
• The wikipedia page (en.wikipedia.org/wiki/Tutte_polynomial#Gaussian_elimination) seems to make the rather vague assertion that all evaluations for which the Tutte polynomial is computable in polynomial time are actually determinants or Pfaffians. – Sam Hopkins Jun 10 '15 at 0:55
• Remotely related question about interpolating the Tutte polynomial from the hyperbola: mathoverflow.net/questions/173259/… – joro Jun 10 '15 at 11:48