Kirchhoff's theorem

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem is a theorem about the number of spanning trees in a graph. It states that this number can be computed as any cofactor of the graph's Laplacian matrix. This shows in particular that the number of spanning trees can be computed from the graph data in polynomial time. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. The theorem is named after the German mathematician Gustav Kirchhoff, who published it in 1847. An English translation of Kirchhoff's paper was published in 1958.