Sergei K. Lando

Tutte decomposition for graphs, weighted graphs,
and symmetric matrices

Deleting and contracting a link in a graph
determines an equivalence relation in the Abelian
group freely generated by graphs: modulo this relation a graph is
equivalent to the sum of itself with deleted edge
and itself with contracted edge. Tutte's theorem states that
any graph is equivalent to a unique linear combination of
graphs without links. We call this linear combination
the {\it Tutte decomposition\/} of the original graph.
Recent developments in knot theory and the theory of
Abelian avalanches and sandpiles involve the Tutte decomposition
for graphs with weighted vertices and edges. We prove that
this decomposition is also unique and discuss the Hopf algebra
structures underlying it.