Lesson 7

For an arbitrary matrix \(B\), let \(B_{i}\) (\(B_{i;j}\)) denote the matrices obtained from \(B\) by deleting the \(i\)-th row (respectively, the \(i\)-th row and the \(j\)-th column). Then \(L_{i;i}=(I_{i})(I_{i}^{T})\).

Now everything is ready for the formulation and proof of the main result of this section, the matrix-tree theorem.

Theorem (Kirchhoff, 1847). Let \(G(V,E)\) be a graph with \(n \ge 2\) vertices, \(i \in [n]\), and let \(L\) be the Kirchhoff matrix of \(G\). Then \[\tau(G)=\det(L_{i;i}) \ .\]