The Tutte polynomial of a graph G is a widely-studied and very useful graph invariant. It’s a polynomial in two variables x, y that extends, among other things, the chromatic and flow polynomials of a graph. In a certain (well-defined) sense, it’s actually the most general object that obeys what’s called the deletion-contraction recurrence, which I’ll talk about in a bit. One particular specialization of the Tutte polynomial of interest is its value at x = 1, y = 0. This has at least two useful combinatorial interpretations; it counts the number of acyclic orientations of the edges of G with a fixed unique source, or, equivalently, it counts what are called the “maximal parking functions” of G. As it happens, this second interpretation is the one I’m most interested in, but the first is more useful for this discussion, so we’ll only consider it here. Throughout this post, we’ll let M(G) = T_G(1,0) be the Tutte polynomial evaluated at (1, 0). (more…)