Editing Spanning tree (section)

===Tutte polynomial===
{{main|Tutte polynomial}}

The [[Tutte polynomial]] of a graph can be defined as a sum, over the spanning trees of the graph, of terms computed from the "internal activity" and "external activity" of the tree. Its value at the arguments (1,1) is the number of spanning trees or, in a disconnected graph, the number of maximal spanning forests.<ref>{{harvtxt|Bollobás|1998}}, p. 351.</ref>

The Tutte polynomial can also be computed using a deletion-contraction recurrence, but its [[Computational complexity theory|computational complexity]] is high: for many values of its arguments, computing it exactly is [[Sharp-P-complete|#P-complete]], and it is also hard to approximate with a guaranteed [[approximation ratio]]. The point (1,1), at which it can be evaluated using Kirchhoff's theorem, is one of the few exceptions.<ref>{{Citation
|last1=Goldberg | first1= L.A. | author1-link = Leslie Ann Goldberg
|last2=Jerrum | first2=  M.
|author2-link=Mark Jerrum
|title= Inapproximability of the Tutte polynomial
|journal=Information and Computation
| doi=10.1016/j.ic.2008.04.003
|year=2008
|volume=206
|pages=908–929
|issue=7
|arxiv=cs/0605140
}}; {{Citation
| last1= Jaeger |first1= F.
|last2= Vertigan | first2=  D. L.
|last3= Welsh | first3  =D. J. A.|author-link3=Dominic Welsh
| title= On the computational complexity of the Jones and Tutte polynomials
|journal=Mathematical Proceedings of the Cambridge Philosophical Society
| volume= 108|pages = 35–53
| doi= 10.1017/S0305004100068936
| year= 1990
|issue= 1
|bibcode= 1990MPCPS.108...35J
}}.</ref>