A note on chain lengths and the Tutte polynomial (Q952642)

Replace an edge in a graph \(G\) by a set of edges in series, that is, by a path. This operation is also known as a sequence of subdivisions. The resulting graph is homeomorphic to \(G\). The authors show that the number of chains of a given length can be easily found by the Tutte polynomial. Hence two Tutte-equivalent graphs will have the same distribution of chain lengths. They give two applications of this statement. They also give dual results for the number of multiple edges given their multiplicity.