computed as where the sum is over all n–k-element subsets of . For example 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 submatrix of the incidence matrix corresponds bijectively to a k-component spanning forest with a choice of vertex for each component. The coefficients are up to sign the coefficients of the characteristic polynomial of Q. See also List of topics related to trees Markov chain tree theorem Minimum spanning tree Prüfer sequence References . . . External links A proof of Kirchhoff's theorem Algebraic graph theory Spanning tree Theorems in graph theory Gustav Kirchhoff