The number of distinct spanning trees of a connected graph equals any cofactor of the graph's Laplacian matrix. Proved by Gustav Kirchhoff in the context of electrical circuit theory, it gives an exact algebraic formula for a fundamental graph-counting problem.
Facts
StatementKirchhoff'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. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Proved By
Source Kirchhoff's Theorem (Wikipedia)
In the Other Atlases
Credited To
Also in Science Atlas: credited with this subject.
Sources
1. Kirchhoff's Theorem (Wikipedia)
Wikimedia Foundationlead paragraph, opening two sentences
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.
lead paragraph, sentence naming the publication year
The theorem is named after the German mathematician Gustav Kirchhoff, who published it in 1847.
In Group: Graph Theory, Lead section
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree
Proved By: Gustav Kirchhoff, Lead
The theorem is named after the German mathematician Gustav Kirchhoff, who published it in 1847.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.