Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

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

share|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 M. Jun 14 '13 at 8:33
1  
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
add comment

Your Answer

 
discard

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.