Intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem using as little matrices/linear algebra as possible?

could someone provide me/refer me to a intuitive idea/proof behind Kirchhoff's Matrix Tree Theorem that uses as little technical details involving matrices/linear algebra as possible? I'm trying to give a group of talented high schoolers who haven't seen matrices before a sketch/cursory proof of the result, but I couldn't think of a good way to explain it.

• Given that Kirchhoff's matrix tree theorem has a determinant in the statement, I'm not sure what you can expect. – Yuval Filmus Jul 9 '15 at 17:30
• wikipedia Kirchoff thm with few-paragraph proof outline – vzn Jul 9 '15 at 21:31
• Wikipedia's proof outline (which is missing a central part) is heavy on linear algebra. The combinatorial proof is instead heavy on combinatorics. – Yuval Filmus Jul 9 '15 at 21:44

The algebraic proof goes like this. Fix a number of vertices $n$, and consider the "formal Laplacian" $n \times n$ matrix defined by \begin{align*} L(i,i) &= \sum_{j \neq i} X(i,j) \\ L(i,j) &= - X(i,j). \end{align*} Here the $X(i,j)$ are commuting indeterminates. For every spanning tree $T$ of the complete graph $K_n$ we can associate a degree $n-1$ monomial $X(T)$ as follows. Root the tree at the vertex $n$. For every non-root vertex $i$ with parent $j$, we include the variable $X(i,j)$ in the monomial. In total $X(T)$ is a product of $n-1$ monomials, one for every edge in the tree.

Let $M$ be the $(n,n)$ minor of $L$. We will show that $\det M = \sum_T X(T)$. You can derive the matrix-tree theorem from this statement by substituting the actual graph for the indeterminates $X(i,j)$. If you wish, you can run the entire proof after doing the substitution, and then you don't have to talk about indeterminates.

Recall that $$\det M = \sum_{\pi \in S_{n-1}} (-1)^\pi \prod_{i=1}^{n-1} M_{i\pi(i)}.$$ We can write every permutation $\pi$ as a product of cycles $\pi_1,\ldots,\pi_{\ell(\pi)}$ and of fixed points $F(\pi)$, and then we get \begin{align*} \det M &= \sum_\pi (-1)^\pi \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} (-X(i,\pi(i))) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right) \\ &= \sum_\pi (-1)^{\ell(\pi)} \prod_{t=1}^{\ell(\pi)} \prod_{i \in \pi_t} X(i,\pi(i)) \prod_{i \in F(\pi)} \left(\sum_{j \neq i} X(i,j)\right), \end{align*} using the formula $(-1)^\pi = \prod_{t=1}^{\ell(\pi)} (-1)^{|\pi_t|+1}$. We can rewrite this as $$\det M = \sum_\pi D(\pi),$$ where $D(\pi)$ is the expression appearing above.

If we open up all the sums, we find that $\det M$ is a (weighted) sum of monomials of the form $X(\alpha) = \prod_{i=1}^{n-1} X(i,\alpha(i))$. For each $\alpha$, we can look at the directed graph in which $i$ points at $\alpha(i)$. It's not hard to see that each such graph consists of a (possibly empty) collection of cycles $\alpha_1,\ldots,\alpha_{\ell(\alpha)}$ and a tree $T(\alpha)$ rooted at $n$. We will show that the coefficient of $X(\alpha)$ equals $1$ if $\ell(\alpha) = 0$, and vanishes otherwise. This will complete the proof.

Consider first the case that $\ell(\alpha) = 0$. In this case the only permutation $\pi$ for which $X(\alpha)$ appears in $D(\pi)$ is the identity permutation (since every $X(\beta)$ appearing in any other $D(\pi)$ contains some cycle), ans so the coefficient of $X(\alpha)$ in $\det M$ is indeed $1$.

Next, consider the case in which $\ell = \ell(\alpha) \neq 0$. In this case, for every subset $S$ of the cycles of $T(\alpha)$, $X(\alpha)$ appears in $D(\pi)$ for $\pi = \pi(S)$ which consists of the cycles in $S$, and it only appears in these $D(\pi)$. For every $S$, the coefficient of $X(\alpha)$ in $D(\pi(S))$ is $(-1)^{|S|}$. Therefore the total coefficient of $X(\alpha)$ in $\det M$ is $$\sum_{S \subseteq \{\alpha_1,\ldots,\alpha_\ell\}} (-1)^{|S|} = \sum_{S_1 \subseteq \{\alpha_1\}} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_1| + \cdots + |S_\ell|} = \\ \sum_{S_1 \subseteq \{\alpha_1\}} (-1)^{|S_1|} \cdots \sum_{S_\ell \subseteq \{\alpha_\ell\}} (-1)^{|S_\ell|} = (1-1)^\ell = 0.$$ (This is just inclusion-exclusion. The previous case is the case $\ell=0$.) This completes the proof.

This proof is taken from lecture notes by Jacques Verstraete. See also Mark Muldoon's lecture notes, which presents this argument as a version of inclusion-exclusion.

• great, but probably well outside the range of "talented high schoolers" & likely even most undergraduates! – vzn Jul 9 '15 at 21:30
• @vzn Not necessarily. You can add lots of pictures to make it clearer, consider only the case of 0 or 1 cycles (of $\alpha$) to make it simpler, and use concrete examples involving small $n$ to make it tangible. Of course, since a determinant is involved, the students (or undergraduates) need to have some background, in this case they need to understand the concept of sign of a permutation. – Yuval Filmus Jul 9 '15 at 21:42