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. Matroids The spanning trees of a graph form the bases of a graphic matroid, so Kirchhoff's theorem provides a formula to count the number of bases in a graphic matroid. The same method may also be used to count the number of bases in regular matroids, a generalization of the graphic matroids . Kirchhoff's theorem for directed multigraphs Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows: The entry qi,j for distinct i and j equals −m, where m is the number of edges from i to j; The entry qi,i 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 ith row and column of Q. Counting spanning k-component forests Kirchhoff's theorem can be generalized to count -component spanning forests in an unweighted graph. A -component spanning forest is a subgraph with 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 , define its weight to be the product of the number of vertices in each component. Then where the sum is over all -component spanning forests and is the coefficient of of the polynomial The last factor in the polynomial is due to the zero eigenvalue . More explicitly, the number can be