Pretty much exactly what it says on the tin. Let G be a connected graph; then the Tutte polynomial T_G(x,y) carries a lot of information about G. However, it obviously doesn't encode everything about the graph, since there are examples of non-isomorphic graphs with the same Tutte polynomial.
My question is, what information exactly does the Tutte polynomial encapsulate? I'm aware of a few answers to this question, but I don't find any of them particularly satisfying. For instance, T_G(x,y) can be characterized as "the universal Tutte-Grothendieck invariant," but the definition of Tutte-Grothendieck invariants is just as unintuitive as the definition of the Tutte polynomial (because it's essentially the same definition!) One can also define the coefficients as counting certain spanning trees of G, but this doesn't make apparent the fact that the Tutte polynomial specializes to the chromatic polynomial, or the notion that it carries most of the information one can obtain via linear algebra methods.
So is there a nice way of thinking about what data about G the Tutte polynomial encodes?
ETA: Okay, here's a very rough conjecture. Suppose that there's some "computationally simple" (i.e., testing membership is in NP) class of graphs such that there are two connected graphs G, H with the same Tutte polynomial, and G is in the class and H is not. Then there are spanning trees S, T of G, H respectively, such that S is in the class and T is not.
This would mean, in a sense that I can't make entirely rigorous, that the information about a graph G not encoded in the Tutte polynomial is just information about the structure of spanning trees of G. (Update: As Kevin Costello points out in a comment, this idea appears to be severely limited by the existence of certain pairs of co-Tutte graphs. In particular, we would need to count spanning trees with multiplicity for it to have even a chance of being true.)
As stated, the above conjecture is false for trivial reasons. But is there a way of making it true, perhaps by requiring the property to be, in some sense, natural? Is there a broad notion of "graph properties" for which it is true? Can we at least state a conjecture along these lines which does seem to be true?
Best Answer
No-one so far has mentioned matroids. The Tutte polynomial encodes some of the information from the cycle matroid of the graph. Two graphs with the same cycle matroid (and number of vertices) have the same Tutte polynomials. So if a graph property is not determined by the cycle matroid (and the number of vertices) then it can't be obtained from the Tutte polynomial.