Editing Kirchhoff's theorem (section)

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