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: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (10)

Label	Occurrences
Matrix-Tree theorem	2
Kirchhoff polynomial	1
Kirchhoff tree polynomial	1
Kirchhoff’s matrix-tree theorem	1
Kirchhoff’s theorem on trees	1
Matrix-Tree theorem for directed graphs	1
all-minors matrix-tree theorem	1
directed matrix-tree theorem	1
matrix-tree theorem canonical	1
weighted matrix-tree theorem	1

How this entity was disambiguated

This entity first appeared as the object of triple T9838898 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: matrix-tree theorem
Context triple: [de Bruijn–van Aardenne–Ehrenfest theorem, relatedTo, matrix-tree theorem]

A. Sylvester determinant
The Sylvester determinant is a mathematical construct introduced by James Joseph Sylvester, typically referring to a determinant associated with resultants and elimination theory in algebra.
B. Cauchy determinant
The Cauchy determinant is a classical determinant formula in linear algebra that gives a closed-form expression for matrices with entries of the form 1/(x_i + y_j), named after the French mathematician Augustin-Louis Cauchy.
C. Cayley–Hamilton theorem
The Cayley–Hamilton theorem is a fundamental result in linear algebra stating that every square matrix satisfies its own characteristic polynomial.
D. Cauchy matrix
A Cauchy matrix is a structured matrix whose entries are defined by the reciprocals of pairwise differences of two sequences, widely used in numerical analysis, interpolation, and algebra.
E. Pólya enumeration theorem
The Pólya enumeration theorem is a fundamental result in combinatorics that counts distinct configurations of objects under group actions by using cycle index polynomials and generating functions.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: matrix-tree theorem
Target entity description: 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.

A. Sylvester determinant
The Sylvester determinant is a mathematical construct introduced by James Joseph Sylvester, typically referring to a determinant associated with resultants and elimination theory in algebra.
B. Cauchy determinant
The Cauchy determinant is a classical determinant formula in linear algebra that gives a closed-form expression for matrices with entries of the form 1/(x_i + y_j), named after the French mathematician Augustin-Louis Cauchy.
C. Cayley–Hamilton theorem
The Cayley–Hamilton theorem is a fundamental result in linear algebra stating that every square matrix satisfies its own characteristic polynomial.
D. Cauchy matrix
A Cauchy matrix is a structured matrix whose entries are defined by the reciprocals of pairwise differences of two sequences, widely used in numerical analysis, interpolation, and algebra.
E. Pólya enumeration theorem
The Pólya enumeration theorem is a fundamental result in combinatorics that counts distinct configurations of objects under group actions by using cycle index polynomials and generating functions.
F. None of above. chosen

Statements (45)

Predicate	Object
instanceOf	result in algebraic graph theory ⓘ theorem ⓘ
alsoKnownAs	Kirchhoff’s matrix-tree theorem ⓘ linked to: matrix-tree theorem Kirchhoff’s theorem on trees ⓘ linked to: matrix-tree theorem
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 ⓘ
gives	number of spanning trees of a graph ⓘ
hasVariant	all-minors matrix-tree theorem ⓘ linked to: matrix-tree theorem directed matrix-tree theorem ⓘ linked to: matrix-tree theorem weighted matrix-tree theorem ⓘ linked to: matrix-tree theorem
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 ⓘ
proofTechniques	Cauchy–Binet formula ⓘ combinatorial arguments ⓘ linear algebra ⓘ
relatedTo	Kirchhoff’s circuit laws ⓘ linked to: Kirchhoff's circuit laws Laplacian eigenvalues ⓘ Matrix-Tree theorem for directed graphs ⓘ linked to: matrix-tree theorem
relatesConcept	Kirchhoff matrix ⓘ linked to: graph Laplacian cofactor ⓘ determinant ⓘ graph Laplacian ⓘ 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 ⓘ

How these facts were elicited