Editing Kirchhoff's theorem (section)

=== Explicit enumeration of spanning trees ===

Kirchhoff's theorem can be strengthened by altering the definition of the Laplacian matrix. Rather than merely counting edges emanating from each vertex or connecting a pair of vertices, label each edge with an [[Indeterminate (variable)|indeterminate]] and let the (''i'', ''j'')-th entry of the modified Laplacian matrix be the sum over the indeterminates corresponding to edges between the ''i''-th and ''j''-th vertices when ''i'' does not equal ''j'', and the negative sum over all indeterminates corresponding to edges emanating from the ''i''-th vertex when ''i'' equals ''j''.

The determinant of the modified Laplacian matrix by deleting any row and column (similar to finding the number of spanning trees from the original Laplacian matrix), above is then a [[homogeneous polynomial]] (the Kirchhoff polynomial) in the indeterminates corresponding to the edges of the graph. After collecting terms and performing all possible cancellations, each [[monomial]] in the resulting expression represents a spanning tree consisting of the edges corresponding to the indeterminates appearing in that monomial. In this way, one can obtain explicit enumeration of all the spanning trees of the graph simply by computing the determinant.

For a proof of this version of the theorem see Bollobás (1998).<ref>{{cite book | last=Bollobás | first=Béla | title=Modern graph theory | series=Graduate Texts in Mathematics | publisher=Springer | publication-place=New York | year=1998| volume=184 | isbn=978-0-387-98488-9 | doi=10.1007/978-1-4612-0619-4 }}</ref>