Paper detail

The Tutte expansion revisited

The Tutte polynomial of a connected graph was originally defined by Tutte as a sum over all spanning trees of monomials depending on a fixed linear order on the set of edges. Tuttle proved that while these monomials do depend on the linear order, the sum does not. The present paper is a result of a reflection upon this classical theorem of Tutte. It is devoted to an elementary and detailed proof of this theorem in its natural generality, i.e. not for graphs, but for matroids. In contrast with usual methods, the emphasis is on the properties of maps (as opposed to elements) naturally associated to a matroid (or a graph) and an order. In order to fully explain the four-fold symmetry of the proof, we introduce notion of linking between two matroids on the same set. While every matroid is, in fact, linked only to itself and to its dual matroid, the notion of a linking identifies the essential features of the theory and allows to replace the usual four similar arguments by a single one. This is done in Theorem 9.1, which is the focal point of the present paper. With the exception of Introduction, the present paper is self-contained modulo basic concepts related to sets and maps. In particular, no knowledge of the matroid theory or of the graph theory is assumed.