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](http://www.m-hikari.com/ams/ams-password-2009/ams-password45-48-2009/shirdarehAMS45-48-2009.pdf) claim that it is due to Kirchhoff, but I was not able to find the statement [in his paper on the subject](http://gallica.bnf.fr/ark:/12148/bpt6k15157m/f515.image))


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



History of deletion-contraction formula
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**](http://dx.doi.org/10.1215/S0012-7094-40-00718-9), Duke Math. J. 7, 312-340 (1940). [ZBL0024.16501](https://zbmath.org/?q=an:0024.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**](http://dx.doi.org/10.1016/S0196-8858(03)00041-1), Adv. Appl. Math. 32, No. 1-2, 5-9 (2004). [ZBL1041.05001](https://zbmath.org/?q=an:1041.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. 


