2012/07/30 by Saad Quader, Quader, Saad
Computer Science · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Management and Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Theory and Algorithms #Spectral Theory (math.SP)
paper · pdf · doi:10.48550/arxiv.1207.7033
openalex publication_date 2012/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
(DRAFT VERSION) In this article we present a proof of the famous Kirchoff's Matrix-Tree theorem, which relates the number of spanning trees in a connected graph with the cofactors (and eigenvalues) of its combinatorial Laplacian matrix. This is a 165 year old result in graph theory and the proof is conceptually simple. However, the elegance of this result is it connects many apparently unrelated concepts in linear algebra and graph theory. Our motivation behind this work was to make the proof accessible to anyone with beginner\slash intermediate grasp of linear algebra. Therefore in this paper we present proof of every single argument leading to the final result. For example, we prove the elementary properties of determinants, relationship between the roots of characteristic polynomial (that is, eigenvalues) and the minors, the Cauchy-Binet formula, the Laplace expansion of determinant, etc.