Matrix Tree Theorem

The matrix tree theorem, also called Kirchhoff's matrix-tree theorem (Buekenhout and Parker 1998), states that the number of nonidentical spanning trees of a graph G is equal to any cofactor of its Laplacian matrix (Skiena 1990, p. 235).

See also

Laplacian Matrix, Spanning Tree

Explore with Wolfram|Alpha


Buekenhout, F. and Parker, M. "The Number of Nets of the Regular Convex Polytopes in Dimension <=4." Disc. Math. 186, 69-94, 1998.Chaiken, S. "A Combinatorial Proof of the All-Minors Matrix Tree Theorem." SIAM J. Alg. Disc. Methods 3, 319-329, 1982.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, p. 38, 1998.Kirchhoff, G. "Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird." Ann. Phys. Chem. 72, 497-508, 1847.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 235, 1990.

Referenced on Wolfram|Alpha

Matrix Tree Theorem

Cite this as:

Weisstein, Eric W. "Matrix Tree Theorem." From MathWorld--A Wolfram Web Resource.

Subject classifications