Editing Spanning tree (section)

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