Medial graph

For a plane graph G, twice the evaluation of the Tutte polynomial at the point (3,3) equals the sum over weighted Eulerian orientations in the medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation (that is, the number of vertices with incident edges cyclically ordered "in, out, in out").

[5] Since the Tutte polynomial is invariant under embeddings, this result shows that every medial graph has the same sum of these weighted Eulerian orientations.

The medial graph definition can be extended to include an orientation.

Using the directed medial graph, one can effectively generalize the result on evaluations of the Tutte polynomial at (3,3).

For a plane graph G, n times the evaluation of the Tutte polynomial at the point (n+1,n+1) equals the weighted sum over all edge colorings using n colors in the directed medial graph of G so that each (possibly empty) set of monochromatic edges forms a directed Eulerian graph, where the weight of a directed Eulerian orientation is 2 to the number of monochromatic vertices.