Editing Kirchhoff's theorem (section)

{{Short description|On the number of spanning trees in a graph}}
{{confused|Kirchhoff's integral theorem}}
In the [[mathematics|mathematical]] field of [[graph theory]], '''Kirchhoff's theorem''' or '''Kirchhoff's matrix tree theorem''' named after [[Gustav Kirchhoff]] is a theorem about the number of [[spanning tree]]s in a [[graph (discrete mathematics)|graph]], showing that this number can be computed in [[polynomial time]] from the [[determinant]] of a [[submatrix]] of the graph's [[Laplacian matrix]]; specifically, the number is equal to ''any'' [[Cofactor (linear algebra)|cofactor]] of the Laplacian matrix. Kirchhoff's theorem is a generalization of [[Cayley's formula]] which provides the number of spanning trees in a [[complete graph]].

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which is equal to the difference between the graph's [[degree matrix]] (the [[diagonal matrix]] of vertex [[degree (graph theory)|degree]]s) and its [[adjacency matrix]] (a [[(0,1)-matrix]] with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).

For a given [[connectivity (graph theory)|connected]] graph ''G'' with ''n'' labeled [[vertex (graph theory)|vertices]], let ''λ''<sub>1</sub>,&nbsp;''λ''<sub>2</sub>,&nbsp;...,&nbsp;''λ<sub>n</sub>''<sub>−1</sub> be the non-zero [[eigenvalue]]s of its Laplacian matrix. Then the number of spanning trees of ''G'' is

:<math>t(G) = \frac{1}{n} \lambda_1\lambda_2\cdots\lambda_{n-1}\,.</math>

An English translation of Kirchhoff's original 1847 paper was made by J. B. O'Toole and published in 1958.<ref>{{cite journal | last=O'Toole | first=J.B.| journal=IRE Transactions on Circuit Theory |title=On the Solution of the Equations Obtained from the Investigation of the Linear Distribution of Galvanic Currents | date=1958| volume=5| issue=1 | pages=4–7 | doi=10.1109/TCT.1958.1086426 }}</ref>