matrix-tree theorem

E824090

result in algebraic graph theory theorem

The matrix-tree theorem is a fundamental result in algebraic graph theory that expresses the number of spanning trees of a graph as a determinant of a matrix derived from the graph’s Laplacian.

Try in SPARQL Jump to: Statements Referenced by

Statements (45)

Predicate	Object
instanceOf	result in algebraic graph theory ⓘ theorem ⓘ
alsoKnownAs	Kirchhoff’s matrix-tree theorem NERFINISHED ⓘ Kirchhoff’s theorem on trees NERFINISHED ⓘ
appearsIn	textbooks on algebraic graph theory ⓘ textbooks on spectral graph theory ⓘ
appliesTo	finite graph ⓘ multigraph ⓘ simple graph ⓘ
assumes	graph is connected for a positive number of spanning trees ⓘ
coreClaim	any cofactor of the Laplacian matrix equals the number of spanning trees of the graph ⓘ deleting any one row and any one column from the Laplacian and taking the determinant yields the number of spanning trees ⓘ
field	algebraic graph theory ⓘ graph theory ⓘ
generalizationOf	Cayley’s formula for the number of labeled trees NERFINISHED ⓘ
gives	number of spanning trees of a graph ⓘ
hasVariant	all-minors matrix-tree theorem NERFINISHED ⓘ directed matrix-tree theorem NERFINISHED ⓘ weighted matrix-tree theorem NERFINISHED ⓘ
historicalPeriod	19th century ⓘ
implies	Laplacian matrix has one zero eigenvalue for a connected graph ⓘ Laplacian matrix of a connected graph has rank n-1 ⓘ
importance	central tool for counting spanning trees ⓘ fundamental theorem in graph enumeration ⓘ
namedAfter	Gustav Kirchhoff NERFINISHED ⓘ
proofTechniques	Cauchy–Binet formula NERFINISHED ⓘ combinatorial arguments ⓘ linear algebra ⓘ
relatedTo	Kirchhoff’s circuit laws NERFINISHED ⓘ Laplacian eigenvalues ⓘ Matrix-Tree theorem for directed graphs NERFINISHED ⓘ
relatesConcept	Kirchhoff matrix NERFINISHED ⓘ cofactor ⓘ determinant ⓘ graph Laplacian NERFINISHED ⓘ spanning tree ⓘ
statementForm	determinant formula ⓘ
usedIn	electrical network theory ⓘ enumeration of spanning trees ⓘ network reliability ⓘ probability on graphs ⓘ random spanning tree algorithms ⓘ spectral graph theory ⓘ
usesMatrix	Laplacian matrix of a graph ⓘ combinatorial Laplacian ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

de Bruijn–van Aardenne–Ehrenfest theorem → relatedTo → matrix-tree theorem ⓘ