# tutte's kirchhoff matrix and the matrix-tree theorem for digraphs

In his books, Tutte tells often of how he and his friends in Cambridge introduced a theory of non-symmetric electricity. His tales are always amusing and enjoyable, but often lack precise references; it does not help, either, that he often published his articles in journals that have little or no internet visibility nowadays.

In particular, I am trying to track back his version of the Matrix-Tree Theorem for digraphs, which makes use of the so-called Kirchhoff matrix - basically, the diagonal matrix of the outdegrees minus the outgoing adjacency matrix, but I am incredibly stuck with his books (it is Theorem VI.27 of his "Graph Theory" book from 1984, for instance). But I cannot believe the theorem is so young. Concerning the Kirchhoff matrix itself, it seems to appear in "The dissection of equilateral triangles into equilateral triangles" from 1948. Maybe even earlier?

Can anybody help?

-

## 1 Answer

I have a copy of the two volumes "Selected Papers of W. T. Tutte" in which his (self-selected) best papers are reprinted with a short commentary preceding each paper.

He has the following things to say, the first quote relevant to the directed theorem, and the second to the original theorem.

Re: The dissection of equilateral triangles into equilateral triangles (1948)

".. we find a proof of the directed form of the Matrix-Tree theorem. Perhaps this is the most important theorem of the paper, though I did not realize it at the time."

Re: The dissection of rectangles into squares (1940)

"There seems to be some confusion as to where the Matrix-Tree theorem was first stated. Some say in the paper we are discussing. I think howeve [sic] that Kirchhoff stated it clearly enough in the terminology of his time."

-
Thank you! I have just checked the first paper (I am finally vistiting a university where it is available) and it seems that the Kirchhoff matrix is defined in it (§2.10), although not under the name "Kirchhoff". Unfortunately I am still outside the relevant paywall for the earlier paper. Is it clear whether the directed version of the MTT (and hence also the Kirchhoff matrix) are presented there, too. – Delio Mugnolo Jun 14 '13 at 8:33
The 1940 paper has the undirected theorem with arbitrary weights on the edges. The old-fashioned language make it hard to understand immediately, but I'm pretty sure the directed version is not there. – Brendan McKay Jun 14 '13 at 11:58