For any graph G , let be the number of spanning trees of G , be the line graph of G , and for any nonnegative integer r , be the graph obtained from G by replacing each edge e by a path of length connecting the two ends of e . In this article, we obtain an expression for in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if G is of order and size in which s vertices are of degree 1 and the others are of degree k . Thus we prove a conjecture on for such a graph G .
No takes yet. Share an insight, caveat, or question.
A 2016 study studied this question.