On enumeration of spanning subgraphs with a preassigned cyclomatic number in a graph (Q1207353)

Let \(G\) be a labelled undirected graph with no loops but with parallel edges allowed (multigraph), and let \(\sigma_ n(G)\) be the number of connected spanning subgraphs of \(G\) with cyclomatic number (number of edges -- number of vertices +1) equal to \(n\). Choose any pair of vertices which are joined by \(m\geq 1\) edges, and let \(\hat eG\) (respectively, \(\dot eG)\) be the graph obtained from \(G\) by deleting (respectively, contracting) all the edges joining these two vertices. The following recursive formula is stated, and a special case of it is derived: \[ \sigma_ n(G)=\sigma_ n(\hat eG)+\sum^{n+1}_{i=1}{m\choose n+2- i}\sigma_{i-1}(\dot eG). \] This generalizes the non-recursive formulae given in \textit{C. J. Liu} and \textit{Y. Chow} [Enumeration of connected spanning subgraphs of a planar graph, Acta Math. Hung. 41, 27-36 (1983; Zbl 0517.05044)] for \(\sigma_ n(G)\), where \(G\) is a planar graph, and in \textit{G. Kirchhoff} [Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72, 497-508 (1847)] for \(\sigma_ 0(G)\), where \(G\) is an arbitrary graph. Reviewer's remarks: In the formula in the paper, the vertices are assumed to be the ones with the highest labels, but if these are not adjacent the formula reads \(\sigma_ n(G)=\sigma_ n(G)\). The letter \(\chi\), which usually means chromatic number, is used for the cyclomatic number instead of the usual letter \(\nu\). No reference is given to Kirchhoff's paper or any other source of this formula. And the examples cannot be followed without first reading the aforementioned paper of C. J. Liu and the author.