A Characterization of the Tutte Polynomial via Combinatorial Embeddings

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original denition given by Tutte as the generating function of spanning trees counted according to activities. Tutte's notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We dene a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial equals the generating function of spanning trees counted according to embedding-activities. This generating function is, in fact, independent of the embedding