Definition
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.
Related concepts
(0,1)-matrixAdjacency matrixBEST theoremBijectionCauchy–Binet formulaCayley's formulaCharacteristic polynomialCofactor (linear algebra)Complete graphComponent (graph theory)Degree (graph theory)Degree matrixDeterminantDiagonal matrixDiamond graphDimension (vector space)Eigenvalues and eigenvectorsForest (graph theory)Graph (discrete mathematics)Graph theoryGraphic matroidGustav KirchhoffHomogeneous polynomialIncidence matrixIndeterminate (variable)Kirchhoff's integral theoremLaplacian matrixList of graph theory topicsLoop (graph theory)Markov chain tree theoremMathematical inductionMathematicsMinimum spanning treeMonomialMultigraphOriented incidence matrixPolynomial timePrüfer sequenceRegular matroidSpanning treeTransposeTree (graph theory)Undergraduate Texts in Mathematics
7 concepts already in your glossary