History of deletion-contraction formula

Question

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.

Answer 1

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.

Answer 2

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)