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.

Definitions and statement