Editing Spanning tree (section)

===Deletion-contraction===
If ''G'' is a graph or [[multigraph]] and ''e'' is an arbitrary edge of ''G'', then the number ''t''(''G'') of spanning trees of ''G'' satisfies the ''deletion-contraction recurrence''
''t''(''G'')&nbsp;=&nbsp;''t''(''G''&nbsp;−&nbsp;''e'')&nbsp;+&nbsp;''t''(''G''/''e''), where ''G''&nbsp;−&nbsp;''e'' is the multigraph obtained by deleting ''e''
and ''G''/''e'' is the [[Edge contraction|contraction]] of ''G'' by ''e''.<ref>{{harvtxt|Kocay|Kreher|2004}}, p.&nbsp;109.</ref> The term ''t''(''G''&nbsp;−&nbsp;''e'') in this formula counts the spanning trees of&nbsp;''G'' that do not use edge&nbsp;''e'', and the term ''t''(''G''/''e'') counts the spanning trees of&nbsp;''G'' that use&nbsp;''e''.

In this formula, if the given graph ''G'' is a [[multigraph]], or if a contraction causes two vertices to be connected to each other by multiple edges,
then the redundant edges should not be removed, as that would lead to the wrong total. For instance a [[bond graph]] connecting two vertices by ''k'' edges has ''k'' different spanning trees, each consisting of a single one of these edges.