Editing Spanning tree (section)

==Counting spanning trees==
[[File:Cayley's formula 2-4.svg|thumb|[[Cayley's formula]] counts the number of spanning trees on a complete graph. There are <math>2^{2-2}=1</math> trees in <math>K_2</math>,
<math>3^{3-2}=3</math> trees in <math>K_3</math>, and <math>4^{4-2}=16</math>
trees in <math>K_4</math>.]]

The number ''t''(''G'') of spanning trees of a connected graph is a well-studied [[invariant (mathematics)|invariant]].

===In specific graphs===
In some cases, it is easy to calculate ''t''(''G'') directly:
* If ''G'' is itself a tree, then {{math|1=''t''(''G'')&nbsp;=&nbsp;1}}.
* When ''G'' is the [[cycle graph]] ''C<sub>n</sub>'' with ''n'' vertices, then {{math|1=''t''(''G'')&nbsp;=&nbsp;''n''}}.
* For a [[complete graph]]  with ''n'' vertices, [[Cayley's formula]]<ref>{{citation
 | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
 | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
 | pages = 141–146
 | publisher = [[Springer-Verlag]]
 | title = Proofs from THE BOOK
 | year = 1998| title-link = Proofs from THE BOOK }}.</ref> gives the number of spanning trees as {{math|1=''n''<sup>''n''&nbsp;−&nbsp;2</sup>}}.
* If ''G'' is the [[complete bipartite graph]] <math>K_{p,q}</math>,then <math>t(G)=p^{q-1}q^{p-1}</math>.<ref name="pearls" />
* For the ''n''-dimensional [[hypercube graph]] <math>Q_n</math>,<ref>{{citation
 | last1 = Harary | first1 = Frank | author1-link = Frank Harary
 | last2 = Hayes | first2 = John P.
 | last3 = Wu | first3 = Horng-Jyh
 | doi = 10.1016/0898-1221(88)90213-1
 | issue = 4
 | journal = Computers & Mathematics with Applications
 | mr = 949280
 | pages = 277–289
 | title = A survey of the theory of hypercube graphs
 | volume = 15
 | year = 1988| hdl = 2027.42/27522
 | hdl-access = free
 }}.</ref> the number of spanning trees is <math>t(G)=2^{2^n-n-1}\prod_{k=2}^n k^{{n\choose k}}</math>.

===In arbitrary graphs===
{{main|Kirchhoff's theorem}}

More generally, for any graph ''G'', the number ''t''(''G'') can be calculated in [[polynomial time]] as the [[determinant]] of a [[matrix (mathematics)|matrix]] derived from the graph,
using [[Kirchhoff's theorem|Kirchhoff's matrix-tree theorem]].<ref>{{citation |title=Graphs, Algorithms, and Optimization |series=Discrete Mathematics and Its Applications |first1=William |last1=Kocay |first2=Donald L. |last2=Kreher |publisher=CRC Press |year=2004 |isbn=978-0-203-48905-5 |pages=111–116 |contribution=5.8 The matrix-tree theorem |url=https://books.google.com/books?id=zxSmHAoMiRUC&pg=PA111}}.</ref>

Specifically, to compute ''t''(''G''), one constructs the [[Laplacian matrix]] of the graph, a square matrix in which the rows and columns are both indexed by the vertices of ''G''. The entry in row ''i'' and column ''j'' is one of three values:
* The degree of vertex ''i'', if ''i''&nbsp;=&nbsp;''j'',
* −1, if vertices ''i'' and ''j'' are adjacent, or
* 0, if vertices ''i'' and ''j'' are different from each other but not adjacent.
The resulting matrix is [[singular matrix|singular]], so its determinant is zero. However, deleting the row and column for an arbitrarily chosen vertex leads to a smaller matrix whose determinant is exactly&nbsp;''t''(''G'').

===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.

===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>