MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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."

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.