Editing Kirchhoff's theorem (section)

== Particular cases and generalizations ==

=== Cayley's formula ===
{{main|Cayley's formula}}
[[Cayley's formula]] follows from Kirchhoff's theorem as a special case, since every vector with 1 in one place, −1 in another place, and 0 elsewhere is an eigenvector of the Laplacian matrix of the complete graph, with the corresponding eigenvalue being ''n''.  These vectors together span a space of [[dimension (vector space)|dimension]] ''n''&nbsp;−&thinsp;1, so there are no other non-zero eigenvalues.

Alternatively, note that as Cayley's formula gives the number of distinct labeled trees of a complete graph ''K<sub>n</sub>'' we need to compute any cofactor of the Laplacian matrix of ''K<sub>n</sub>''. The Laplacian matrix in this case is
:<math>\begin{bmatrix}
  n-1 & -1      & \cdots & -1      \\
  -1  & n-1     & \cdots & -1      \\
  \vdots & \vdots& \ddots & \vdots \\
  -1 & -1      & \cdots & n-1      \\
\end{bmatrix}.</math>

Any cofactor of the above matrix is ''n<sup>n</sup>''<sup>−2</sup>, which is Cayley's formula.

=== Kirchhoff's theorem for multigraphs ===

Kirchhoff's theorem holds for [[multigraph]]s as well; the matrix ''Q'' is modified as follows:
* The entry ''q<sub>i,j</sub>'' equals −''m'', where ''m'' is the number of edges between ''i'' and ''j'';
* when counting the degree of a vertex, all [[loop (graph theory)|loop]]s are excluded.
Cayley's formula for a complete multigraph is {{nowrap|''m''<sup>''n''−1</sup>(''n''<sup>''n''−1</sup>−(''n''−1)''n''<sup>''n''−2</sup>)}} by same methods produced above, since a simple graph is a multigraph with ''m'' = 1.

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

=== Matroids ===
The spanning trees of a graph form the bases of a [[graphic matroid]], so Kirchhoff's theorem provides a formula for the number of bases in a graphic matroid. The same method may also be used to determine the number of bases in [[regular matroid]]s, a generalization of the graphic matroids {{harv|Maurer|1976}}.

=== Kirchhoff's theorem for directed multigraphs ===
Kirchhoff's theorem can be modified to give the number of oriented spanning trees in directed multigraphs.
The matrix ''Q'' is constructed as follows:
* The entry ''q<sub>i,j</sub>'' for distinct ''i'' and ''j'' equals −''m'', where ''m'' is the number of edges from ''i'' to ''j'';
* The entry ''q<sub>i,i</sub>'' equals the indegree of ''i'' minus the number of loops at ''i''.
The number of oriented spanning trees rooted at a vertex ''i'' is the determinant of the matrix gotten by removing the ''i''th row and column of ''Q''

=== Counting spanning ''k''-component forests ===
Kirchhoff's theorem can be generalized to count {{mvar|k}}-component spanning [[forest (graph theory)|forest]]s in an unweighted graph.<ref>{{cite book |  author=Biggs, N. | title=Algebraic Graph Theory | publisher=Cambridge University Press | year=1993}}</ref> A {{mvar|k}}-component spanning forest is a subgraph with {{mvar|k}} [[Component (graph theory)|connected components]] that contains all vertices and is cycle-free, i.e., there is at most one path between each pair of vertices. Given such a forest ''F'' with connected components <math display="inline">F_1, \dots, F_k</math>, define its weight <math display="inline">w(F) = |V(F_1)| \cdot \dots \cdot |V(F_k)|</math> to be the product of the number of vertices in each component. Then
:<math>\sum_F w(F) = q_k,</math>

where the sum is over all {{mvar|k}}-component spanning forests and <math display="inline">q_k</math> is the coefficient of <math display="inline">x^k</math> of the polynomial
:<math>(x+\lambda_1) \dots (x+\lambda_{n-1}) x.</math>
The last factor in the polynomial is due to the zero eigenvalue <math display="inline">\lambda_n=0</math>. More explicitly, the number <math display="inline">q_k</math> can be computed as
:<math>q_k = \sum_{\{i_1, \dots, i_{n-k}\}\subset\{1\dots n-1\}} \lambda_{i_1} \dots \lambda_{i_{n-k}}.</math>
where the sum is over all ''n''−''k''-element subsets of <math display="inline">\{1, \dots, n\}</math>. For example

<math>\begin{align}
q_{n-1} &= \lambda_1 + \dots + \lambda_{n-1} = \mathrm{tr} Q = 2|E| \\
q_{n-2} &= \lambda_1\lambda_2 + \lambda_1 \lambda_3 + \dots + \lambda_{n-2} \lambda_{n-1} \\
q_{2} &= \lambda_1 \dots \lambda_{n-2} + \lambda_1 \dots \lambda_{n-3} \lambda_{n-1} + \dots + \lambda_2 \dots \lambda_{n-1}\\
q_{1} &= \lambda_1 \dots \lambda_{n-1} \\
\end{align}</math>

Since a spanning forest with ''n''−1 components corresponds to a single edge, the ''k'' = ''n''−1 case states that the sum of the eigenvalues of ''Q'' is twice the number of edges. The ''k'' = 1 case corresponds to the original Kirchhoff theorem since the weight of every spanning tree is ''n''.

The proof can be done analogously to the proof of Kirchhoff's theorem. An invertible <math>(n-k) \times (n-k)</math> submatrix of the incidence matrix corresponds [[bijection|bijectively]] to a ''k''-component spanning forest with a choice of vertex for each component.

The coefficients <math display="inline">q_k</math> are up to sign the coefficients of the [[characteristic polynomial]] of ''Q''.