10
$\begingroup$

The following is known as deletion-contraction formula:

Assume $\Gamma$ is a connectted graph with edge $\rho$ then $$t(\Gamma)=t(\Gamma\backslash\rho)+t(\Gamma/\rho),$$ where $\Gamma\backslash\rho$ is $\Gamma$ with the edge $\rho$ removed and $\Gamma/\rho$ obtained from $\Gamma$ by contracting $\rho$ and $t(\Gamma)$ is the number of spanning trees in $\Gamma$.

The statement appear as Proposition 4.9 in Graph Theory by Bondy Murty with no reference. (Haghighi and Bibak claim that it is due to Kirchhoff, but I was not able to find the statement in his paper on the subject)

I wonder who made this observation first, or at least what is the earlies reference to this.

$\endgroup$
15
$\begingroup$

This seems to have first been observed in

Brooks, R.L.; Smith, C.A.B.; Stone, A.H.; Tutte, W.T., The dissection of rectangles into squares, Duke Math. J. 7, 312-340 (1940). ZBL0024.16501.

See equation 3.12 and Theorem 3.13 in the paper. I found a discussion of this in a survey paper of Tutte:

Tutte, W.T., Graph-polynomials, Adv. Appl. Math. 32, No. 1-2, 5-9 (2004). ZBL1041.05001.

Tutte indicates in this paper that these coauthors discovered the deletion-contraction relation for spanning trees. The similarity with the deletion-contraction relation for the chromatic polynomial then led Tutte to define the two variable Tutte polynomial. So this seems to pin down the origin of this formula.

$\endgroup$
8
$\begingroup$

Not exactly a reference, but I found some discussion of this formula in Bill Tutte's graph-theoretic memoirs, Graph Theory as I Have Known it (Oxford, 1998). In Chapter 5 ("Algebra in Graph Theory"), he writes:

In their study of complexities or tree-numbers the Four made much use of the recursion formula $$C(G) = C(G'_A) + C(G''_A)$$ When I was doing my PhD research I began to collect other functions of graphs that satisfied similar recursions. (p.53)

The "Four" that Tutte is referring to here are: R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte. (He mentions that they all met as students at Cambridge in the Trinity Mathematical Society.) So perhaps this deletion-contraction formula was folklore at the time, or at least "Fourlore".

I think that the connection to Kirchhoff's theorem is indirect, corresponding to the fact that the "complexity" and the "tree-number" of a graph coincide. Tutte explains in Chapter 1 ("Squaring the square"):

We learned that Kirchhoff's Laws for a network $N$ were associated with a special matrix $K(N)$ called, by us at least, the Kirchhoff matrix of $N$. [...] We learned that the determinant of the matrix $K_i(N)$ obtained from $K(N)$ by striking out the $i$th row and column was independent of $i$. We decided to call its value the "complexity" $C(N)$ of $N$. (p.7)

[...]

By expanding a determinant it can be shown that the number of spanning trees of $G$ is the complexity $C(G)$ of $G$. For a general electrical network $N$ the complexity $C(N)$ proves to be the sum over all the spanning trees of $N$ of the products of the conductances of their edges. This result is known as the Matrix-Tree Theorem, and it goes back to Kirchhoff. (p.11)

$\endgroup$
  • 3
    $\begingroup$ Posted this answer before seeing that Ian Agol found an explicit reference! I will leave it up though, for the links to the historical discussion by Tutte. $\endgroup$ – Noam Zeilberger May 4 '17 at 19:21
  • 1
    $\begingroup$ This looks similar to the discussion in the "graph-polynomials" paper I linked to. $\endgroup$ – Ian Agol May 4 '17 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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