Enumeration of acyclic walks in a graph (Q686419)

Acyclic walk of a graph is a closed walk whose projection is a tree. Let \(S\) be a subtree of \(G\). Denote by \(v_ 1,\ldots,v_{t_ S}\) those vertices of \(G-S\) which are adjacent with vertices of \(S\) in \(G\). Let \(g_ i\) denote the number of vertices of \(S\) adjacent with \(v_ i\), \(1 \leq i \leq t_ S\). Let \(\omega_ \ell(G)\) and \(\omega_ \ell^{ac}(G)\) denote the number of closed and acyclic walks of \(G\), respectively, with length \(\ell\). It is shown that \(\omega_ \ell^{ac}(G)=\sum_ Sm(S)\cdot \omega_ \ell(S)\), where \(S\) goes over all subtrees of \(G\), and \(m(S)=\prod^{t_ S}_{i=1}(1-g_ i)\).