Lesson 9

Proof. [Proof of the matrix tree theorem] The theorem follows from the lemma in a few lines. \[\begin{align*}\det(L_{i;i})&=\det(I_{i}I_{i}^{T})\\&=\sum_{S \in \binom{E}{n-1}}\det(I_{i}[S]) \det(I_{i}[S]^{T})\\&=\tau(G) \ .\end{align*}\]◼